Cracking Coding Interview - 5.5 Debugger

Debugger: Explain what the following code does: ((n & (n - 1)) == 0).

Hints: #157, #202, #261, #302, #346, #372, #383, #398

解法

当以下情况时这段代码返回true：

1. n是2的次方，且n > 1的时候
2. 或者，n是0

两个数字AND结果为0代表两个数字没有一个1在相同的位置。

当你在给二进制做减法的时候，实际上是把最右边的1变成0，把它右边的0都变成1。

1
2
3
4

       rightmost 1
           v
n:     xxxx100
n - 1: xxxx011

当(n & (n - 1)) == 0就意味着这个n里最右边的1的左边没有1了，也就是说只有一个1，这就意味着n是2的次方。