使用位操作来判断无符号整数是否可以以2 ^ n-1的形式表示

Question

要测试无符号整数是否属于2^n-1我们使用的形式:

x&(x+1)

那应该是什么？那是,

x&(x+1) == ?

Answer 1

许多形式2^n-1将所有位都设置为第n位.例如,2^3-1(7)是:

0b0111

如果我们添加一个,我们得到8:

0b1000

然后,执行按位,我们看到我们得到零,因为两个数字都没有设置位.如果我们从不是表单的数字开始2^n+1,那么结果将是非零的.

Answer 2

作为现有答案的补充,这里有一个简短的解释,为什么x不是形式0b00000(零)或0b0111..11(所有最低位设置,这些都是n> 0的数字2 ^ n-1)的数字不具有财产x&(x+1) == 0.

对于多个x形式0b????1000..00,x+1具有与x最低有效位相同的数字,因此x & (x+1)至少有一个位设置,显示为设置的位x.通过简短的解释:

x       0b????1000..00
x+1     0b????1000..01
x&(x+1) 0b????10000000

对于许多x形式0b????10111..11:

x       0b????10111..11
x+1     0b????110000000
x&(x+1) 0b????10000..00

总之,如果x不是零或以二进制形式写入所有最低位,则x&(x+1)不是零.

Answer 3

零.如果X是2 ^ N-1,则它是二进制的1的完整字符串.除此之外是1后跟一串与X相同长度的零,因此这两个数字在任何位置都没有共同的1位,因此两者的AND为零.