binary - 你如何得到 x 的值，使得 "(x-1) & x" 和 "(x-1) % 131071" 都为零？

Question

最近在一次采访中被问到如何列出所有x这样的

((((x - 1) & x) == 0) && ((x - 1) % 131071 == 0))

其中x是一个 64 位无符号整数。

我被告知总共 4 个整数，如何获得所有 4 个值x？

最好采取什么方法？

Answer 1

((x - 1) & x) == 0)意味着它x要么是零，要么是 2 的幂（请参阅this bit twiddling hack）。它之所以有效，是因为 2 的幂表示为单个 1 位，后跟任意数量的 0 位（假设N它们）。

而且，当您减去一个时，您总是会得到一个正好是N1 位的数字，因此将它们组合在一起：

100000...000
 11111...111
------------
000000...000

总是给你零。零当然是一种特殊情况，因为与零相加给你零：

0000000...000
1111111...111
-------------
0000000...000

由于这是一个编程问答网站，请参阅此程序：

#include <stdio.h>
int main (void) {
    unsigned long long x = 0;
    unsigned long long oldx = x;

    while (x >= oldx) {
        if ((((x - 1ULL) & x) == 0) && (((x - 1ULL) % 131071ULL) == 0))
            printf ("%llu\n", x);
        oldx = x;
        x = (x == 0ULL) ? 1ULL : x * 2ULL;
    }

    return 0;
}

它生成以下四个值（不是您建议的三个值）：

1
131072
17179869184
2251799813685248