编程语言中的操作符 编程语言中的操作符 Table of contents
あかやあかしやあやかしの
当初我第一次看到这道题的时候，因为用的是 Java，所以首先想到的是 unsigned right shift 然后再 left shift 回来的结果如果相同的话说明这一位为 0，不同则为 1，然后用同样的方法判断下一位直到数字本身为 0。假设数字一共有 n 比特，那么时间复杂度为 O(n)，最好情况是 O(1)。
但事实上如果用 mask 的话有更快一点的方案。我们知道 x & 1可以推断出最右位是 1 还是零，那么只要执行一个 n 次的循环，然后将数字不断向左 shift 判断每一位直到数字本身为 0 即可，这样的话时间复杂度也为 O(n)，但从执行一右一左 shift 变成了只需要执行一次 AND 操作。
更高阶的解法需要一些对位运算的了解。将新数字与原数字相 AND 得到的数字，除最末位的 1 变成 0 之外，都与一开始的原数字相同，比如10100111 & 10101000 = 10100000，至此我们跳过了所有末尾 0，只执行了一次操作就判断出了一个 1
假设数字中有 m 个 1，那么时间复杂度为 O(m)，所以要优于之前的解法。