0x00 原理

将 2 的幂次方写成二进制形式后，很容易就会发现有一个特点：二进制中只有一个 1 ，并且 1 后面跟了 N 个 0。

因此问题可以转化为判断 1 后面是否跟了 N 个 0 就可以了。

如果将这个数减去 1 后会发现，仅有的那个 1 会变为 0，而原来的那 N 个 0 会变为 1。

因此将原来的数与去减去1后的数字进行与运算后会发现为零。

最快速的方法：

(number & number - 1) == 0

比方说，8 和 7 的二进制分别是 1000 和 0111，那么两者相与则会得到 0，即这个数是 2 的幂次。

1000
0111
———
0000

0x01 代码解释

我们利用二进制的位置左右移，来实现除以 2 的简单方法。

下面的代码，是一个计算输入数字是 2 的几次幂，若不是 2 的幂次则返回 -1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def log2(num):
    if num & (num - 1) != 0:
        return -1
    count = 0
    while num > 1:
        num = num >> 1
        count += 1
    return count


print(log2(1))  # 0
print(log2(2))  # 1
print(log2(10))  # -1
print(log2(1024))  # 10

0x02 简单扩展

如何求一个数 N 的二进制中 1 的个数？

利用上面 num & (num - 1) 的性质，我们可以很好地消除最右边的 1（每次相与）。

我们只需要循环消除掉最右边的 1（直到 num 为 0 ），我们就可以得到最终 1 的个数。

1
2
3
4
5
6
7
8
9
10
11
def count_1(num):
    count = 0
    while num:
        num = num & (num - 1)
        count += 1
    return count

print(count_1(1))  # 1 | 1
print(count_1(7))  # 3 | 111
print(count_1(10))  # 2 | 1010
print(count_1(231))  # 6 | 11100111

0x03 Reference

快速判断一个数是否是2的幂次方，若是，并判断出来是多少次方！- CSDN