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

Question

为了测试无符号整数是否为2^n-1的形式，我们使用：

x&(x+1)

这句话的意思是什么？也就是说，

x&(x+1) == ?

- user466534

Answer 1

形如2^n-1的数字将会在第n位之前所有的二进制位都被设置为1。例如，2^3-1 (7) 的二进制表示为：

0b0111

如果我们在此基础上加1，就会得到8：

0b1000

然后，进行按位与操作，我们发现结果为零，因为两个数字的任何一个二进制位都没有被设置。如果我们使用不是形如2^n+1的数字开始，则结果将不为零。

- James McNellis

---

我认为你在开头的意思是 2^n-1。 - Michael Mrozek

虽然你和另一个回答者很好地解释了为什么x&(x+1)==0对于x是2^n-1的形式是必要的，但你们两个都没有提到这个属性的充分性。换句话说，为什么一个不是以0b0111..11写成的数字x不能具有属性x&(x+1)==0？ - Pascal Cuoq

@Pascal：如果您想回答并详细说明，我很乐意为这样的答案点赞。 :-) - James McNellis

@James 我已经起草了一个简短的解释。 - Pascal Cuoq

Answer 2

除了现有的答案，以下是为什么数字x不是0b00000（零）或0b0111..11（所有最低位均设置，这些是2^n-1的所有数字，n>0）形式时，不具备x&(x+1)==0属性的简短解释。

对于一个形如0b????1000..00的数字x，x+1的数字与x相同，除了最低有效位，因此x&(x+1)至少有一位被设置，即在x中被显示为已设置的位。简而言之：

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

对于某个形如 0b????10111..11 的数 x：

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

总之，如果x既不是零，也不是用所有最低位设置的二进制书写的，则x&(x+1)不为零。

- Pascal Cuoq

Answer 3

零。如果X是2的N次方减1，那么它在二进制中是一个由1组成的连续字符串。比它多一的数字是一个以1开头，长度与X相同的0字符串，因此这两个数字在任何位置都没有相同的1位，所以它们的AND结果为零。

- JustJeff