2的幂的除法和乘法

Question

我在一篇论文中读到，一个数除以 2 的幂的乘法是一个微不足道的过程。我在互联网上搜索了很多解释，但没有得到它。任何人都可以用简单的语言解释这实际上意味着什么。

Answer 1

从位操作的角度来看，这是微不足道的。乘以 2 相当于左移 1 位，除法是右移。类似地，乘以和除以 2 的任何幂也很简单。

int a = 123;           // or in binary format: a = 0b01111011;

assert (a * 2) == (a << 1);   // 2 = 2^1, (a << 1) = 11110110
assert (a / 2) == (a >> 1);   // 2 = 2^1, (a >> 1) = 00111101

assert (a * 8) == (a << 3);   // 8 = 2^3, (a << 3) = 1111011000
assert (a / 8) == (a >> 3);   // 8 = 2^3, (a >> 3) = 0000001111

另请注意a*2 = a+a，加法有时甚至比移位更便宜，具体取决于硬件。

对于有符号除法，请注意在某些语言（例如 C）中，整数除法会向零截断，而算术右移（将符号位的副本移入 2 的补码）总是向 -Infinity 取整。例如(-5)/2 == -2，但是(-5) >> 1 == -3。实现有符号除以 2 仍然可以通过移位 + 额外操作来完成，以添加符号位以获得截断行为。（查看 C 编译器输出。）