Làm thế nào để bạn thực hiện XOR bằng cách sử dụng + - * /?

Question

Làm cách nào để thao tác XOR (trên hai bit int 32) chỉ được thực hiện bằng cách sử dụng các phép tính số học cơ bản? Bạn có phải làm điều đó bitwise sau khi chia cho mỗi quyền lực của 2 lần lượt, hoặc là có một phím tắt? Tôi không quan tâm đến tốc độ thực thi quá nhiều về mã đơn giản nhất, ngắn nhất.

Chỉnh sửa: Đây không phải là bài tập về nhà, mà là câu đố đặt ra trên hacker.org. Vấn đề là để thực hiện XOR trên một máy ảo dựa trên stack với các hoạt động rất hạn chế (tương tự như ngôn ngữ brainfuck và có - không có thay đổi hoặc mod). Sử dụng VM đó là một phần khó khăn, mặc dù tất nhiên là dễ dàng hơn bởi một thuật toán ngắn và đơn giản.

Trong khi giải pháp của FryGuy là thông minh, tôi sẽ phải đi với lý tưởng ban đầu của tôi (tương tự như giải pháp của litb) vì so sánh khó sử dụng trong môi trường đó.

Answer 1

Tôi xin lỗi tôi chỉ biết tiến lên phía trước một thẳng trong đầu:

uint32_t mod_op(uint32_t a, uint32_t b) { 
    uint32_t int_div = a/b; 
    return a - (b * int_div); 
} 

uint32_t xor_op(uint32_t a, uint32_t b) { 
    uint32_t n = 1u; 
    uint32_t result = 0u; 
    while(a != 0 || b != 0) { 
     // or just: result += n * mod_op(a - b, 2); 
     if(mod_op(a, 2) != mod_op(b, 2)) { 
      result += n; 
     } 
     a /= 2; 
     b /= 2; 
     n *= 2; 
    } 
    return result; 
} 

Giải pháp thay thế trong ý kiến ​​có thể được sử dụng thay cho nếu để tránh phân nhánh. Nhưng sau đó một lần nữa, giải pháp không phải là chính xác nhanh chóng và nó làm cho nó trông lạ mắt :)

Answer 2

Tôi không biết điều này có đánh bại được điểm của câu hỏi hay không, nhưng bạn có thể thực hiện XOR với AND, OR và NOT , như sau:

uint xor(uint a, uint b) { 
    return (a | b) & ~(a & b); 
} 

Trong tiếng Anh, đó là "a hoặc b, chứ không phải a và b", ánh xạ chính xác với định nghĩa của XOR.

Tất nhiên, tôi không gắn bó chặt chẽ với quy định của bạn chỉ sử dụng toán tử số học, nhưng ít nhất điều này là một sự thực hiện đơn giản, dễ hiểu.

Answer 3

Sẽ dễ dàng hơn nếu bạn có AND vì

A HOẶC B = A + B - (A và B)

Một XOR B = A + B - 2 (A và B)

int customxor(int a, int b) 
{ 
    return a + b - 2*(a & b); 
} 

Answer 4

tôi sẽ làm điều đó một cách đơn giản:

uint xor(uint a, uint b):  

uint ret = 0; 
uint fact = 0x80000000; 
while (fact > 0) 
{ 
    if ((a >= fact || b >= fact) && (a < fact || b < fact)) 
     ret += fact; 

    if (a >= fact) 
     a -= fact; 
    if (b >= fact) 
     b -= fact; 

    fact /= 2; 
} 
return ret; 

có thể có một cách dễ dàng hơn, nhưng tôi không biết của ai.