簡化Z = X ^（X << Y）函數的逆函數

我很難將以下函數簡化爲幾個原子二進制運算，但感覺像是可能的，但是我無法做到這一點，「M抓我的頭幾個小時了：簡化Z = X ^（X << Y）函數的逆函數

public UInt32 reverse_xor_lshift(UInt32 y, Int32 shift) 
{ 
    var x = y & (UInt32)((1 << shift) - 1); 

    for (int i = 0; i < (32 - shift); i++) { 
     var bit = ((x & (1 << i)) >> i)^((y & (1 << (shift + i))) >> (shift + i)); 

     x |= (UInt32)(bit << (shift + i)); 
    } 

    return x; 
}

函數的功能就是它計算Z = X^(X << Y)的倒數，換句話說reverse_xor_lshift(Z, Y) == X

來源

2015-07-20 Lu4

你可以用少得多的操作逆它，但在通過使用與在converting back from grey code中使用的相同的技術更難以理解的方式：

應用轉換z ^= z << i其中i從shift開始並且每次迭代都加倍。

僞代碼：

while (i < 32) 
    x ^= x << i 
    i *= 2

這工作，因爲在第一個步驟中，您異或最低位（影響），通過他們在那裏「在異或運算」的地方，因此，「異或出來」。然後，更改爲原件的部分寬度是其兩倍。新號碼的格式爲x^(x << k)^(x << k)^(x << 2k) = x^(x << 2k)，它又是一樣的東西，但是具有兩倍的偏移量，所以同樣的技巧將再次起作用，解碼更多的原始比特。

來源

2015-07-20 16:56:39 harold

令人驚訝的是，George Marsaglia發現了https://en.wikipedia.org/wiki/Xorshift之類的東西。 XorShift RNG的構建塊操作之一是X ^（X >> Y）變換，並且知道它與格雷碼編碼有關，可以從全新的角度看待現有問題，謝謝。 – Lu4

簡化Z = X ^（X << Y）函數的逆函數

回答

相關問題