2的整数次幂？

2的整数次幂的特点

2的整数次幂的数，这里整数我们特指非负整数。
数学表示为$ 2^n, n \in N $，$ N $ 为非负整数（自然数）。我们看看这些数对应的二进制表示：

可以看到，这些数的二进制表示只有一个1，其余位为0。在编程时，2的n次幂的数可以使用数字1左移n位，即1 << n。
如果将这个数减去1，便从最高的1位往下，全变为1了。用$2^3 = 8$举例：

1
2
3
4

  00001000
- 00000001
-----------
  00000111

判断一个数是否为2的n次幂

根据2的n次幂的二进制特点，我们可以知道，如果这个数x，与(x - 1)求逻辑与，结果为0时，则这个数时2的n次幂的数：

1
2

def is_power_of_two(n):
    return not (n & (n - 1))

但是，上面的程序遇到n = 0时，也认为它是2的n次幂的。所以需要改进一下：

1
2

def is_power_of_two(n):
    return not (n & (n - 1)) and n

因为n为0的情况相对较少，所以把and n条件放在后面。
用c语言写起来可能更清爽：

1
2

int is_power_of_two(int n):
    return !(n & (n - 1)) && n

较大的2的整数次幂的数

问题描述

求一个数临近的、且较大的2的整数次幂的数，示例：

一个简单的求解方法

用python脚本举例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def simple_roundup(n):
    final_n = 1
    tmp_n = n >> 1

    while tmp_n != 0:
        final_n <<= 1
        tmp_n >>= 1

    if n > final_n:
        final_n <<= 1

    return final_n

该方法是最容易想到的，利用二进制找最高位的1。原数右移一位，如果不为0，说明还有1，被求解数就左移一次。
代码简单，但求解过程中运算次数不确定。比如输入0，while循环直接跳过；如果输入256，循环将执行8次。如果函数被大量调用，且输入都是更大的数，必然导致运算量增大。那么可以怎么优化呢？

利用求解数特点来优化

先上代码，长得帅的可能一看就明白了。一段只支持8 bit表示的数（如果数更大，请手动扩展）：

1
2
3
4
5
6

def roundup(n):
    n = n - 1
    n |= n >> 1
    n |= n >> 2
    n |= n >> 4
    return n + 1

边界0、会触及溢出的大数需要特殊处理。这个程序更多瞄准非边界的数。

现在无论求什么数，只需要相同几步即可求解。
用数字65来模拟代码运行，为了方便查看，我用-代替0：

通过类似模拟，程序的基本思路就是先把数转化位-1111111的形式，最后+1得到10000000，即为所求。
为了正确求解8、64等2的n次幂的数，第一行使用n = n - 1做一下适配。

现在看为什么右移1、2、4呢？从表中可以看出（描述中所谓的最高位，特指从二进制表示时为1的高位开始算；保证n位为1特指如果从最高1位开始，如果还有n位的空余，那么这些空余位上都是1）：

• n |= n >> 1 保证数的最高2位都是1
• n |= n >> 2 最高2位都是1，所以再右移2位，求或之后保证得到最高4位为1
• n |= n >> 4 最高4位都是1，所以再右移4位，求或之后保证得到最高8位为1
• 如果是32 bit表示的数，那么追加n |= n >> 8 和n |= n >> 16。更大的数，以此类推。

这个问题的实际应用

为什么程序员要浪费时间来优化这个方法？求得2的n次幂的数又有什么用？难道仅仅是炫技好玩？又或者为了求职面试？

其实最好用的场景就是取模运算。
人类世界倾向与十进制计数，计算机基于电路开闭的基本设计，倾向于二进制计数。
对于十进制世界的人类来说，求任意一个整数的相对于10的3次幂的模，比如7625 % (10^3)，只用取低位值625便可，非常简单。但对于计算机来说，这个计算会稍微麻烦一点。
而让计算机求一个数相对于2的3次幂的模，比如14 % (2^3)，计算机也可以取最低3位值00001110 & (000001000 - 1) = 00001110 & 00000111 = 00000110 = 6。但对于人来说，求取又会麻烦一点。

如果我们有一张hash表，需要快速的求key。对于人类来说，我们可以对1000取模，非常方便求取key值。对于计算机来说，对2 ^ 10取模，反而更容易求key。大家可能最容易接触到的场景，就是java的hashmap扩容使用了该方法。

hash取模运算也通常使用素数求模，计算key的速度会慢一点，但是在实际应用中，面对未知数据，或者有潜在规律的数据时，一定程度上减少key冲突的情况，加快查询。这个后面单独写一篇个人见解。

另外，有一些算法也会用到2的n次幂的数。比如一般的FFT快速傅里叶变换中，在分而治之的思想指导下，需要不断的将数据分成2等分。我也是看FFT相关代码才关注这个问题的。

扩展：较小的2的整数次幂的数

借用求“较大”的数的思路，求“较小”的数怎么操作呢？
我写了一段代码，同样要注意边界0、触及溢出的大数要特殊处理，这里只展示主体：

1
2
3
4
5
6

def rounddown(n):
    n >>= 1
    n |= n >> 1
    n |= n >> 2
    n |= n >> 4
    return n + 1

好了，求较小的数有代码了，但我也不知道有什么用，我也不想了，头发快没有了。