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 swapPhiên bản xor mất
real 0m2.068s user 0m2.048s sys 0m0.000sTrườ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.000s143 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 Btuy 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ừ:
Ở đâ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[]; coutb; cout