Mô ta thuật toán để hoán đổi giá trị 2 biến mà không cần sử dụng biến trung gian

answer

Bùi Hồ Nam · Bùi Hồ Nam 13:24 01/12/2009

Sử dụng thuật toán hoán đổi xor

void xorSwap (int* x, int* y) { if (x != y) { //ensure that memory locations are different *x ^= *y; *y ^= *x; *x ^= *y; } }

Tại sao phải thi?

Thử nghiệm là để đảm bảo rằng x và y có các vị trí bộ nhớ khác nhau (thay vì các giá trị khác nhau). Điều này là do (p xor p) = 0và nếu cả x và y chia sẻ cùng một vị trí bộ nhớ, khi một được đặt thành 0, cả hai đều được đặt thành 0. Khi cả * x và * y đều bằng 0, tất cả các hoạt động xor khác trên * x và * y sẽ bằng nhau 0 (vì chúng giống nhau), có nghĩa là hàm sẽ đặt cả * x và * y được đặt thành 0.

Nếu chúng có cùng giá trị nhưng không cùng vị trí bộ nhớ, mọi thứ sẽ hoạt động như mong đợi

*x = 0011 *y = 0011 //Note, x and y do not share an address. x != y *x = *x xor *y //*x = 0011 xor 0011 //So *x is 0000 *y = *x xor *y //*y = 0000 xor 0011 //So *y is 0011 *x = *x xor *y //*x = 0000 xor 0011 //So *x is 0011

Điều này có nên được sử dụng?

Trong trường hợp chung, không. Trình biên dịch sẽ tối ưu hóa biến tạm thời và cho rằng việc hoán đổi là một thủ tục phổ biến, nó sẽ xuất mã máy tối ưu cho nền tảng của bạn.

Lấy ví dụ chương trình kiểm tra nhanh này được viết bằng C.

#include #include #define USE_XOR void xorSwap(int* x, int *y){ if ( x != y ){ *x ^= *y; *y ^= *x; *x ^= *y; } } void tempSwap(int* x, int* y){ int t; t = *y; *y = *x; *x = t; } int main(int argc, char* argv[]){ int x = 4; int y = 5; int z = pow(2,28); while ( z-- ){ # ifdef USE_XOR xorSwap(&x,&y); # else tempSwap(&x, &y); # endif } return x + y; }

Biên dịch bằng cách sử dụng:

gcc -Os main.c -o swap

Phiên bản xor mất

real 0m2.068s user 0m2.048s sys 0m0.000s

Trường hợp như phiên bản với biến tạm thời mất:

real 0m0.543s user 0m0.540s sys 0m0.000s

143 hữu ích 5 bình luận chia sẻ

answer

Lý Triệu Thái · Lý Triệu Thái 13:42 01/12/2009

hình thức chung là:

A = A operation B B = A inverse-operation B A = A inverse-operation B

tuy nhiên, bạn phải có khả năng coi chừng tràn và cũng không phải tất cả các hoạt động đều có nghịch đảo được xác định rõ cho tất cả các giá trị mà thao tác được xác định. ví dụ * và / làm việc cho đến khi A hoặc B bằng 0

xor đặc biệt hài lòng vì nó được định nghĩa cho tất cả các số nguyên và là nghịch đảo của chính nó

85 hữu ích 1 bình luận chia sẻ

answer

Hoàng Sơn Quân · Hoàng Sơn Quân 13:26 01/12/2009

a = a + b b = a - b // b = a a = a - b

78 hữu ích 5 bình luận chia sẻ

answer

Ngô Thanh Trung · Ngô Thanh Trung 17:57 03/12/2009

Không ai đã đề nghị sử dụng std::swap, chưa.

std::swap(a, b);

Tôi không sử dụng bất kỳ biến tạm thời nào và tùy thuộc vào loại avà bviệc triển khai có thể có một đặc tả không. Việc thực hiện nên được viết để biết liệu một 'mẹo' có phù hợp hay không. Không có điểm nào trong việc cố gắng đoán thứ hai.

Nói chung, có lẽ tôi muốn làm một cái gì đó như thế này, vì nó sẽ hoạt động cho các loại lớp cho phép ADL tìm thấy sự quá tải tốt hơn nếu có thể.

using std::swap; swap(a, b);

Tất nhiên, phản ứng của người phỏng vấn về câu trả lời này có thể nói rất nhiều về vị trí tuyển dụng.

73 hữu ích 5 bình luận chia sẻ

answer

Huỳnh Gia Cẩn · Huỳnh Gia Cẩn 13:28 01/12/2009

Như đã được chú ý bởi manu, thuật toán XOR là một thuật toán phổ biến hoạt động cho tất cả các giá trị số nguyên (bao gồm cả con trỏ sau đó, với một số may mắn và đúc). Để hoàn thiện, tôi muốn đề cập đến một thuật toán kém mạnh mẽ hơn với phép cộng / trừ:

A = A + B B = A - B A = A - B

Ở đây bạn phải cẩn thận với tràn / tràn, nhưng nếu không thì nó hoạt động tốt như vậy. Bạn thậm chí có thể thử điều này trên phao / đôi trong trường hợp XOR không được phép trên những cái đó.

17 hữu ích 5 bình luận chia sẻ

answer

Tạ Bích Hậu · Tạ Bích Hậu 14:04 01/12/2009

Những câu hỏi ngu ngốc xứng đáng có câu trả lời thích hợp:

void sw2ap(int& a, int& b) { register int temp = a; // ! a = b; b = temp; }

Việc sử dụng tốt registertừ khóa.

10 hữu ích 4 bình luận chia sẻ

answer

Bùi Ðông Nguyên · Bùi Ðông Nguyên 05:02 22/01/2011

#include #include void main() { int a,b; clrscr(); cout<<"\n==========Vikas=========="; cout<<"\n\nEnter the two no=:"; cin>>a>>b; cout<<"\na"<<a<<"\nb"<<b; a=a+b; b=a-b; a=a-b; cout<<"\n\na="<<a<<"\nb="<<b; getch(); }

2 hữu ích 2 bình luận chia sẻ

answer

Bùi Thiên Lam · Bùi Thiên Lam 17:12 31/01/2014

Vì giải pháp ban đầu là:

temp = x; y = x; x = temp;

Bạn có thể làm cho nó một hai lớp bằng cách sử dụng:

temp = x; y = y + temp -(x=y);

Sau đó làm cho nó một lớp lót bằng cách sử dụng:

x = x + y -(y=x);

2 hữu ích 1 bình luận chia sẻ

answer

Hoàng Quốc Hòa · Hoàng Quốc Hòa 12:16 25/06/2013

Đây là một giải pháp nữa nhưng rủi ro duy nhất.

mã:

#include #include void main() { int a =10 , b =45; *(&a+1 ) = a; a =b; b =*(&a +1); }

mọi giá trị tại vị trí a + 1 sẽ bị ghi đè.

2 hữu ích 3 bình luận chia sẻ

answer

Võ Huy Việt · Võ Huy Việt 09:31 25/01/2011

Nếu bạn thay đổi một chút câu hỏi để hỏi về 2 thanh ghi lắp ráp thay vì các biến, bạn cũng có thể sử dụng xchgthao tác làm một tùy chọn và thao tác ngăn xếp như một thanh ghi khác.

1 hữu ích 1 bình luận chia sẻ

answer

Tạ Phương Thủy · Tạ Phương Thủy 05:58 21/01/2016

Xem xét a=10, b=15:

Sử dụng phép cộng và phép trừ

a = a + b //a=25 b = a - b //b=10 a = a - b //a=15

Sử dụng phép chia và phép nhân

a = a * b //a=150 b = a / b //b=10 a = a / b //a=15

1 hữu ích 2 bình luận chia sẻ

answer

Nguyễn Hồng Thu · Nguyễn Hồng Thu 07:28 11/08/2016

#include using namespace std; int main(void) { int a,b; cout<<"Enter a integer" <<endl; cin>>a; cout<<"\n Enter b integer"<<endl; cin>>b; a = a^b; b = a^b; a = a^b; cout<<" a= "<<a <<" b="<<b<<endl; return 0; }

Cập nhật: Trong phần này, chúng tôi đang lấy đầu vào của hai số nguyên từ người dùng. Sau đó, chúng tôi đang sử dụng thao tác XOR bitwise để trao đổi chúng.

Giả sử chúng ta có hai số nguyên a=4và b=9và sau đó:

a=a^b --> 13=4^9 b=a^b --> 4=13^9 a=a^b --> 9=13^9

1 hữu ích 2 bình luận chia sẻ

answer

Vũ Hà Yên · Vũ Hà Yên 20:00 18/01/2018

Tất nhiên, câu trả lời C ++ nên được std::swap.

Tuy nhiên, cũng không có biến thứ ba trong việc thực hiện sau swap:

template <typename T> void swap (T &a, T &b) { std::pair<T &, T &>(a, b) = std::make_pair(b, a); }

Hoặc, như một lớp lót:

std::make_pair(std::ref(a), std::ref(b)) = std::make_pair(b, a);

1 hữu ích 0 bình luận chia sẻ

answer

Phạm Minh Thy · Phạm Minh Thy 05:50 27/04/2018

Hoán đổi hai số bằng cách sử dụng biến thứ ba như thế này,

int temp; int a=10; int b=20; temp = a; a = b; b = temp; printf ("Value of a", %a); printf ("Value of b", %b);

Hoán đổi hai số mà không sử dụng biến thứ ba

int a = 10; int b = 20; a = a+b; b = a-b; a = a-b; printf ("value of a=", %a); printf ("value of b=", %b);

1 hữu ích 0 bình luận chia sẻ

answer

Phạm Chí Khang · Phạm Chí Khang 10:51 10/02/2011

#include int main() { int a, b; printf("Enter A :"); scanf("%d",&a); printf("Enter B :"); scanf("%d",&b); a ^= b; b ^= a; a ^= b; printf("\nValue of A=%d B=%d ",a,b); return 1; }

0 hữu ích 0 bình luận chia sẻ

answer

Tạ Tấn Dũng · Tạ Tấn Dũng 13:08 16/09/2014

đó là thuật toán hoán đổi XOR chính xác

void xorSwap (int* x, int* y) { if (x != y) { //ensure that memory locations are different if (*x != *y) { //ensure that values are different *x ^= *y; *y ^= *x; *x ^= *y; } } }

bạn phải đảm bảo rằng các vị trí bộ nhớ khác nhau và các giá trị thực tế cũng khác nhau vì A XOR A = 0

0 hữu ích 1 bình luận chia sẻ

answer

Hoàng Uy Việt · Hoàng Uy Việt 11:56 04/07/2016

Bạn có thể làm .... một cách dễ dàng ... trong một dòng Logic

#include int main() { int a, b; printf("Enter A :"); scanf("%d",&a); printf("Enter B :"); scanf("%d",&b); int a = 1,b = 2; a=a^b^(b=a); printf("\nValue of A=%d B=%d ",a,b); return 1; }

hoặc là

#include int main() { int a, b; printf("Enter A :"); scanf("%d",&a); printf("Enter B :"); scanf("%d",&b); int a = 1,b = 2; a=a+b-(b=a); printf("\nValue of A=%d B=%d ",a,b); return 1; }

0 hữu ích 1 bình luận chia sẻ

answer

Lý Hoàng Gia · Lý Hoàng Gia 07:20 16/03/2017

public void swapnumber(int a,int b){ a = a+b-(b=a); System.out.println("a = "+a +" b= "+b); }

0 hữu ích 0 bình luận chia sẻ

answer

Tạ Tân Bình · Tạ Tân Bình 10:54 07/10/2017

Câu trả lời tốt nhất sẽ là sử dụng XOR và sử dụng nó trong một dòng sẽ rất tuyệt.

(x ^= y), (y ^= x), (x ^= y);

x, y là các biến và dấu phẩy giữa chúng giới thiệu các điểm thứ tự để nó không phụ thuộc vào trình biên dịch. Chúc mừng!

0 hữu ích 0 bình luận chia sẻ

answer

Nguyễn Phượng Vũ · Nguyễn Phượng Vũ 14:39 10/08/2017

Chúng ta hãy xem một ví dụ c đơn giản để hoán đổi hai số mà không sử dụng biến thứ ba.

chương trình 1:

#include #include main() { int a=10, b=20; clrscr(); printf("Before swap a=%d b=%d",a,b); a=a+b;//a=30 (10+20) b=a-b;//b=10 (30-20) a=a-b;//a=20 (30-10) printf("\nAfter swap a=%d b=%d",a,b); getch(); }

Đầu ra:

Trước khi trao đổi a = 10 b = 20 Sau khi trao đổi a = 20 b = 10

Chương trình 2: Sử dụng * và /

Hãy xem một ví dụ khác để hoán đổi hai số bằng cách sử dụng * và /.

#include #include main() { int a=10, b=20; clrscr(); printf("Before swap a=%d b=%d",a,b); a=a*b;//a=200 (10*20) b=a/b;//b=10 (200/20) a=a/b;//a=20 (200/10) printf("\nAfter swap a=%d b=%d",a,b); getch(); }

Đầu ra:

Trước khi trao đổi a = 10 b = 20 Sau khi trao đổi a = 20 b = 10

Chương trình 3: Sử dụng toán tử XOR bitwise:

Toán tử XOR bitwise có thể được sử dụng để hoán đổi hai biến. XOR của hai số x và y trả về một số có tất cả các bit là 1 ở bất kỳ bit nào của x và y khác nhau. Ví dụ: XOR của 10 (Trong nhị phân 1010) và 5 (Trong nhị phân 0101) là 1111 và XOR của 7 (0111) và 5 (0101) là (0010).

#include int main() { int x = 10, y = 5; // Code to swap 'x' (1010) and 'y' (0101) x = x ^ y; // x now becomes 15 (1111) y = x ^ y; // y becomes 10 (1010) x = x ^ y; // x becomes 5 (0101) printf("After Swapping: x = %d, y = %d", x, y); return 0;

Đầu ra:

Sau khi hoán đổi: x = 5, y = 10

Chương trình 4:

Không ai đã đề nghị sử dụng std :: exchange, chưa.

std::swap(a, b);

Tôi không sử dụng bất kỳ biến tạm thời nào và tùy thuộc vào loại a và b, việc triển khai có thể có một chuyên môn không. Việc thực hiện nên được viết để biết liệu một 'mẹo' có phù hợp hay không.

Các vấn đề với các phương pháp trên:

1) Cách tiếp cận dựa trên phép nhân và chia không hoạt động nếu một trong các số là 0 khi sản phẩm trở thành 0 không phân biệt số khác.

2) Cả hai giải pháp số học có thể gây ra tràn số học. Nếu x và y quá lớn, phép cộng và phép nhân có thể vượt ra khỏi phạm vi số nguyên.

3) Khi chúng ta sử dụng các con trỏ tới một biến và thực hiện hoán đổi hàm, tất cả các phương thức trên đều thất bại khi cả hai con trỏ trỏ đến cùng một biến. Chúng ta hãy xem điều gì sẽ xảy ra trong trường hợp này nếu cả hai đều trỏ đến cùng một biến.

// Phương pháp dựa trên Bitwise XOR

x = x ^ x; // x becomes 0 x = x ^ x; // x remains 0 x = x ^ x; // x remains 0

// Phương pháp dựa trên số học

x = x + x; // x becomes 2x x = x – x; // x becomes 0 x = x – x; // x remains 0

Hãy cho chúng tôi xem chương trình sau đây.

#include void swap(int *xp, int *yp) { *xp = *xp ^ *yp; *yp = *xp ^ *yp; *xp = *xp ^ *yp; } int main() { int x = 10; swap(&x, &x); printf("After swap(&x, &x): x = %d", x); return 0; }

Đầu ra :

Sau khi trao đổi (& x, & x): x = 0

Trao đổi một biến với chính nó có thể cần thiết trong nhiều thuật toán tiêu chuẩn. Ví dụ: xem triển khai QuickSort này nơi chúng tôi có thể trao đổi một biến với chính nó. Vấn đề trên có thể tránh được bằng cách đặt một điều kiện trước khi hoán đổi.

#include void swap(int *xp, int *yp) { if (xp == yp) // Check if the two addresses are same return; *xp = *xp + *yp; *yp = *xp - *yp; *xp = *xp - *yp; } int main() { int x = 10; swap(&x, &x); printf("After swap(&x, &x): x = %d", x); return 0; }

Đầu ra :

Sau khi trao đổi (& x, & x): x = 10

0 hữu ích 0 bình luận chia sẻ

answer

Lý Hoàng Duy · Lý Hoàng Duy 22:36 28/04/2018

Có thể lạc đề, nhưng nếu bạn biết những gì bạn đang trao đổi một biến duy nhất giữa hai giá trị khác nhau, bạn có thể thực hiện logic mảng. Mỗi khi dòng mã này được chạy, nó sẽ trao đổi giá trị giữa 1 và 2.

n = [2, 1][n - 1]

0 hữu ích 0 bình luận chia sẻ

answer

Dương Trí Liên · Dương Trí Liên 03:45 07/01/2019

Bạn có thể làm:

std::tie(x, y) = std::make_pair(y, x);

Hoặc sử dụng make_tuple khi hoán đổi nhiều hơn hai biến:

std::tie(x, y, z) = std::make_tuple(y, z, x);

Nhưng tôi không chắc liệu bên trong std :: tie có sử dụng biến tạm thời hay không!

0 hữu ích 0 bình luận chia sẻ

answer

Phạm Hương Điệp · Phạm Hương Điệp 19:33 20/02/2013

a = a + b - (b=a);

Nó rất đơn giản, nhưng nó có thể đưa ra một cảnh báo.

1 hữu ích 1 bình luận chia sẻ

answer

Ngô Quốc Bình · Ngô Quốc Bình 19:20 22/06/2014

giải pháp dòng đơn để hoán đổi hai giá trị trong ngôn ngữ c.

a=(b=(a=a+b,a-b),a-b);

1 hữu ích 1 bình luận chia sẻ

Cryto Giá

Mô ta thuật toán để hoán đổi giá trị 2 biến mà không cần sử dụng biến trung gian

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội