按位反转与

Question

这是以下算法：

int encryption(int a, int b) {
    short int c, c2;
    uint8_t d;

    c = a ^ b;
    c2 = c;
    
    d = 0;
    while(c) {
        c &= c - 1;
        d++;
    }
    
    return d;
}

如何找到应该发送到该函数的变量

a

和

b

来决定

d

的输出值？

换句话说，如果我想要 == 11`，我该如何反转算法？

Answer 1

这个：

while(c) {
    c &= c - 1;
    d++;
}

计算

c

中 1 位的数量。例如，如果

c = 10110

，d 将为 3。

这个：

c = a ^ b;

在a和

b

之间做

异或

。这意味着

a

和

b

中共享相同位置的所有1位都将为零，而

a

和

b

中具有不同值的所有位置将变为1。例如：

101110 ^
011010
========
110100

基本上，算法会找到

a ^ b

中 1 位的数量。要强制它输出某个值，只需先按

a = 0

然后按

b = number with d 1-bits

。

要获得

d

1 位的数字，请考虑

b = (2 to the power of d) - 1

。

所以，如果您想要

d = 11

，那么

a = 0

和

b = (2 to the power of 11) - 1 = 2048 - 1 = 2047

。

要以编程方式有效计算 2 的某个幂，请使用以下公式：

2 to the power of k == 1 << k

所以，基本上：

encryption(a, b) == d if a = 0 and b = (1 << d) - 1

。

Answer 2

d

只是

c

中“1”位的数量，请参阅 http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan。

因此，您只需要找到

a

和

b

，使得它们的按位异或值正好有 11 位，例如

a = 0

和

b = 2047

。

（这不是加密。这是一种非常弱的单向哈希。加密必须提供一种方法来取回原始值（解密）。）

Answer 3

我看到它对 XOR b 中的 SET 位进行计数？

好吧，那么我们假设 a==0，b==4095。