将有符号整数除以2的幂

Question

我工作的一种方法,除以2的幂仅使用二进制运算符(<< >> + ^〜&!|)有符号整数,结果必须是圆向着0我碰上了这个问题,也关于问题的Stackoverflow,我无法理解为什么它的工作原理.这是解决方案:

int divideByPowerOf2(int x, int n)
{
    return (x + ((x >> 31) & ((1 << n) + ~0))) >> n;
}

我理解这x >> 31部分(如果x是负数,则只添加下一部分,因为如果它是正数x将自动向0舍入).但令我困扰的是这(1 << n) + ~0部分.它怎么样？

Answer 1

假设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位长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.因此,对n的2次幂的否定具有n个尾随零.

当被除数有n个尾随零并且我们除以2 ^ n时,则不需要将1加到最终商.在任何其他情况下,我们需要添加1.

什么((1 << n)+〜0)正在创建一个具有n个尾随的掩码.

最后几位并不重要,因为我们将向右移动并将它们扔掉.因此,如果除法是精确的,则除数的n个尾随位为零,我们只需添加将被跳过的n 1.相反,如果除法是不精确的,那么被除数的n个尾随位中的一个或多个是1,并且我们肯定会导致进位到n + 1位的位置:这就是我们如何向商加1(我们在红利中添加2 ^ n).这可以解释一下吗？