XORShiftの逆算

XORShiftされた値を逆算する機会がありましたのでメモ書きです。

y = x ^ (x << t)
のとき、y ,t が分かってるとして、xを求めたい。
x << t の値は下位t桁は必ず0になっているから、
y & ((1 << t) - 1) と x & ((1 << t) - 1) は等しい。
また、x << tの t桁 ~ 2*t - 1桁目も y & ((1 << t) - 1) と等しい。
今回は x = 22, t = 3 を例として下記に示す。
x                    = 000010110
x << 3               = 010110000
y                    = 010100110
y & ((1 << 3) - 1)   = ______110
x & ((1 << 3) - 1)   = ______110
x << 3 の 3桁 ~ 5桁目 = ___110___
この時点で判明してるのは、y と x << t の 0桁 ~ 2*t - 1桁目までである。
x << t の判明してる部分をzと置く。XORの性質を利用すると、
z                    = ___110000
y                    = 010100110
x' = z ^ y           = ___010110
よって、x の t桁 ~ 2*t - 1桁目が新たに得られた。
x' << 3              = 010110000
z'                   = 010110000 ; x << tの判明している部分
y                    = 010100110
x'' = z' ^ y         = 000010110
これでxの全ての桁が復元できた。

右シフトのXORShiftもほぼ同様の処理で逆算可能である。
ただし、右シフトは算術シフトか論理シフトで値が異なる点に注意。
ちなみに、C言語の右シフトは算術シフトか論理シフトかは処理系依存。
gccではsignedでは算術シフト、unsignedでは論理シフトになる。

sample code（左シフト）

#include <stdio.h>

// 1 <= t <= 31
unsigned int decodeXORLeftShift(unsigned int y, int t){
    unsigned int x;
    unsigned int z = (y & ((1U << t) - 1)) << t;
    unsigned int mask = ((1U << t) - 1) << t;

    while( mask ){
        x = z ^ y;
        z = z | ((x & mask) << t);
        mask <<= t;
    }
    return x;
}

unsigned int encodeXORLeftShift(unsigned int x, int t){
    return x ^ (x << t);
}

int check(){
    int i;
    unsigned int j;

    for(i=1; i<32; i++){
        for(j=0; j<10000; j++){
            if( j != decodeXORLeftShift(encodeXORLeftShift(j,i), i) ){
                return 0;
            }
        }
    }
    return 1;
}

int main(){
    puts(check() ? "OK" : "NO");
    return 0;
}

実行結果
OK