binary - "(x-1) & x" と "(x-1) % 131071" が両方ともゼロになるような x の値をどのように取得しますか?

Question

最近インタビューで尋ねられたのは、そのxようなものをすべてリストする方法でした。

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

ここxで、 は 64 ビットの符号なし整数です。

合計で 4 つの整数があると言われましたが、4 つの値すべてを取得する方法はx?

どのようなアプローチを取るのが最善でしょうか?

Answer 1

((x - 1) & x) == 0)xは、ゼロまたは 2 の累乗であることを意味します (この bit twiddling hackを参照してください)。これが機能するのは、2 の累乗が単一の 1 ビットとそれに続く任意の数の 0 ビットとして表されるためです (それらについて考えてみましょうN)。

そして、1 を引くと、常に正確にN1 ビットの数値が得られるため、これらを AND 演算します。

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

常にゼロを返します。もちろん、ゼロは特別なケースです。なぜなら、ゼロと何かを論理積するとゼロになるからです。

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

プログラミングQ&Aサイトですので、こちらの番組をご覧ください。

#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;
}

次の4つの値を生成します（提案した3つではありません）：

1
131072
17179869184
2251799813685248