如何使用+ - * /？實現異或

如何使用基本的算術運算來實現XOR操作（在兩個32位整數上）？你是否需要按照每個2的冪數輪流按位分配，還是有捷徑？我並不關心執行速度，而是關於最簡單，最短的代碼。如何使用+ - * /？實現異或

編輯： 這不是作業，而是一個hacker.org構成的謎語。關鍵是在基於堆棧的虛擬機上實施XOR，操作非常有限（類似於brainfuck語言，是 - 不移或mod）。使用該VM是困難的部分，儘管當然通過簡單且簡單的算法變得更容易。

雖然FryGuy的解決方案是聰明的，我會和我當初的理想（類似於litb的解決方案）去，因爲比較難以在環境中使用爲好。

來源

2008-12-17 Michael Borgwardt

你介意移位和模數運算嗎？ – kenny 2008-12-17 00:23:52

x << a === x *（1 << a） x >> a === x /（1 << a） – FryGuy 2008-12-17 01:03:40

聽起來像一個家庭作業問題。我一直認爲這是引用任何外部引用的最佳實踐，但在stackoverflow上引用您自己的問題是非常公平的。什麼是道德困境。 – 2008-12-17 01:03:51

對不起，我只知道向前伸直一個頭：

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; 
}

在評論替代可以用來代替如果以避免分支。但是，然後再次，解決方案是不是很快，也使它看起來很陌生:)

來源

2008-12-17 00:32:32

你必須在最後恢復結果的位。 – 2008-12-17 00:36:41

我不知道這是否是你的問題的重點，但你可以用AND，OR或NOT來實現XOR ，如下所示：

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

在英語中，這是「a或b，但不是a和b」，它與XOR的定義完全對應。

當然，我不是嚴格堅持你只用算術運算符的規定，但至少這是一個簡單的，易於理解的重新實現。

來源

2008-12-17 00:45:35 benjismith

這是更容易，如果你有又因爲

A或B = A + B - （A和B）

A XOR B = A + B - 2（A和B）

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

來源

2008-12-17 01:02:25 ggf31416

我會做的簡單的方法：

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;

有可能是一個更簡單的方法，但我不知道的人。

來源

2008-12-17 02:04:36 FryGuy

如何使用+ - * /？實現異或

回答

相關問題