2 の累乗から 1 を引いたものはすべて 1 です:(2 N - 1 =111....b )
2 = 2^1. 2-1 = 1 (1b)
4 = 2^2. 4-1 = 3 (11b)
8 = 2^3. 8-1 = 7 (111b)
例として 8 を取り上げます。 1000 &0111 =0000
その式は、数値が 2 の累乗でないかどうかをテストします。
最初のケースは 2 0 をチェックします ==1.
その他の場合は num & (num - 1) 出番:
つまり、任意の数値を取得し、1 つ下のビットをマスクすると、次の 2 つのケースのいずれかが得られます。
<オール> <リ>
数値がすでに 2 のべき乗である場合、1 を減らすと、下位ビットのみが設定された 2 進数になります。 & の使用
- 8 の例:
0100 & (0100 - 1)-->(0100 & 0011)-->0000
数値がまだ 2 のべき乗でない場合、1 つ少なくしても最上位ビットに触れないため、結果は 少なくとも になります。 num 未満の最大の 2 のべき乗。
- <リ>
3 の例:0011 & (0011 - 1) --> (0011 & 0010) --> 0010
13 の例:1101 & (1101 - 1) --> (1101 & 1100) --> 1100
したがって、実際の式は、2 0 を含む、2 のべき乗でないすべてのものを検出します。 .
さて、
X =1000 の場合、x-1 =0111 です。1000 &&0111 は 0000 です。
2 のべき乗である各数値 X には、x の位置に 1 を持つ x-1 があり、x にはゼロがあります。また、0 と 1 のビットごとの AND は常に 0 です。
数値 x が 2 の累乗でない場合 (例:0110)。x-1 は 0101 で、 and は 0100 です。
0000 から 1111 までのすべての組み合わせで、
X X-1 X && X-1
0000 1111 0000
0001 0000 0000
0010 0001 0000
0011 0010 0010
0100 0011 0000
0101 0100 0100
0110 0101 0100
0111 0110 0110
1000 0111 0000
1001 1000 1000
1010 1001 1000
1011 1010 1010
1100 1011 1000
1101 1100 1100
1110 1101 1100
1111 1110 1110
また、1 を個別にチェックする必要はありません。