c - 反转 AND 按位

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 的输出值？

换句话说，如果我想要 d=11，我怎样才能反转算法呢？

Answer 1

这个:

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

计算 c 中 1 位的数量.例如，如果 c = 10110 , d 将为 3。

这个:

c = a ^ b;

做 exclusive or在 a 之间和 b .这意味着在 a 中共享相同位置的所有 1 位和 b将为零，所有在 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 .