我正在研究一种仅使用二元运算符 (<< >> + ^ ~ & | !) 将有符号整数除以 2 的幂的方法，结果必须向 0 舍入。我遇到了this question也在关于这个问题的 Stackoverflow 上，但是，我不明白它为什么有效。这是解决方案:
int divideByPowerOf2(int x, int n)
{
return (x + ((x >> 31) & ((1 << n) + ~0))) >> n;
}
我了解 x >> 31部分(仅在 x 为负数时才添加下一部分，因为如果它为正数 x 将自动向 0 舍入)。但困扰我的是 (1 << n) + ~0部分。它是如何工作的？
最佳答案
假设 2 补码，仅将被除数移位相当于某种除法:不是我们将被除数四舍五入到除数的下一个倍数的传统除法。但另一种我们将红利舍入到负无穷大。我在 Smalltalk 中重新发现了这一点，请参阅 http://smallissimo.blogspot.fr/2015/03/is-bitshift-equivalent-to-division-in.html .
例如，让我们将 -126 除以 8。传统上，我们会这样写
-126 = -15 * 8 - 6
但是如果我们向无穷大舍入，我们会得到正余数并写成:
-126 = -16 * 8 + 2
位移是执行第二个操作，就位模式而言(假设 8 位 long int 为短起见):
1000|0010 >> 3 = 1111|0000
1000|0010 = 1111|0000 * 0000|1000 + 0000|0010
那么，如果我们希望传统除法的商向零四舍五入且余数与被除数符号相同怎么办？很简单，我们只需将商加 1 - 当且仅当被除数为负且除法不精确时。
你看到 x>>31 对应于第一个条件，被除数为负，假设 int 有 32 位。
如果除法不精确，则第二项对应于第二个条件。
查看如何将 -1、-2、-4、...编码为两个补码:1111|1111、1111|1110、1111|1100。所以 2 的 n 次方的负数有 n 个尾随零。
当被除数有 n 个尾随零并且我们除以 2^n 时，则不需要在最后的商上加 1。在任何其他情况下，我们需要加 1。
((1 << n) + ~0) 正在做的是创建一个带有 n 个尾随的掩码。
最后 n 位并不重要，因为我们要向右移动并丢弃它们。因此，如果除法是精确的，则被除数的 n 个尾随位为零，我们只需添加 n 个将被跳过的 1。相反，如果除法不精确，则被除数的 n 个尾随位中的一个或多个为 1，我们肯定会导致进位到 n+1 位位置:这就是我们将商加 1(我们将 2^n 添加到股息中)。这样是不是解释得更清楚了？
关于c - 将有符号整数除以 2 的幂，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39691817/