x XOR（x/2）的逆函數是什麼？

Question

x XOR (x/2)的逆向功能是什麼？

是否有對方程求解的規則，類似於代數系統，但與邏輯運算符？

Answer 1

假設我們有N位的數量x。你可以這樣寫：

b(N-1) b(N-2) b(N-3) ... b(0) 

其中b(i)是在數位號i（其中0是最顯著位）。

x/2相同x左移1個比特。我們假設無符號數字。所以：

x/2 = 0 b(N-1) b(N-2) ... b(1) 

現在我們XOR x與x/2：

x^(x/2) = b(N-1)^0 b(N-2)^b(N-1) b(N-3)^b(N-2) ... b(0)^b(1) 

注意，這個最右邊位（最顯著位）爲b(N-1)^0這是b(N-1)。換句話說，你可以從結果中立即得到b(N-1)。當你有這個位時，你可以計算出b(N-2)，因爲結果的第二位是b(N-2)^b(N-1)，你已經知道了b(N-1)。依此類推，您可以計算原始數字x的所有位b(N-1)至b(0)。

Answer 2

我可以給你在比特的算法：

假設你有n比特的數組：

b = [b1 .. bn] // b1-bn are 0 or 1 

原始陣列是：

x0 = b0 
x1 = b1^x0 
x2 = b2^x1 

或一般

x[i] = b[i]^x[i-1] 

Answer 3

Assum E Y = X ^（X/2）

如果你想找到X，這樣做

X = 0 

do 

    X ^= Y 
    Y /= 2 

while Y != 0 

我希望它能幫助！

Answer 4

我知道這是一個老話題，但我偶然發現了同樣的問題，我發現了一個小竅門。如果你有ň位，而不需要ň位操作（如由加斯帕的答案），你可以用的log 2（N）數操作做到這一點，：

假設y是等於x XOR（x/2）在程序開始時，您可以執行以下C程序：

INPUT : y 

int i, x; 
x = y; 
for (i = 1; i < n; i <<= 1) 
    x ^= x >> i; 

OUTPUT : x 

在這裏您可以找到解決方案。

• 「>>」是正確的位移操作。例如，二進制數13,1101（如果右移1）將變爲二進制110，因此13 >> 1 = 6. x >> i相當於x/2^i（在整數中除法，當然）
• 「< <」 是左移位操作（ⅰ< < = 1相當於I * = 2）

爲什麼它的工作？讓我們以如實施例N = 5比特，並且其中y = B4 B3 B2 B1 B0（二進制：在下面的x被寫入二進制也，但我被寫入十進制）開始

• 初始化：

X = B4 B3 B2 B1 B0

• 第一步：I = 1

X >> 1 = B4 B3 B2 B1所以我們有 X = B4 B3 B2 B1 B0 XOR B3 B2 B1 B0 = B4（B3^B4）（B2^B3）（B1^B2）（B 0^B1）

• 第二步驟中：i = 2

x >> 2 >> b4（b3^b4）（b2^b3）所以我們有 x = b4（b3^b4）（b2^b3）（b1^b2）（b0^b1）XOR b4（b3^b4） （B2^B3）= B4（B3^B4）（B2^B3^B4）（B1^B2^B3^B4）（B0^B1^B2^B3）

• 第三步：i = 4的

x >> 4 = b4所以我們有 x = b4（b3^b4）（b2^b3^b4）（b1^b2^b3^b4）（b0^b1^b2^b3）XOR b4 = b4（b3^B4）（B2^B3^B4）（B1^B2^B3^B4）（B0^B1^B2^B3^B4）

• 然後I = 8，這是超過5個，我們退出循環。

而且我們有所需的輸出。

循環有log2（n）次迭代，因爲我從1開始，在每一步乘以2，所以爲了達到n，我們必須做log2（n）次。