用位移位除以2的幂

Question

我有以下任务：

计算x/(2^n)，用于使用位移位的0 <= n <= 30。 要求:圆向零。 示例： divpwr2(15,1) =7 divpwr2(-33,4) = -2 合法经营者：! ~ & ^ | + << >> 最多经营人数: 15人

到目前为止，我得到的是：

public int DivideByPowerOf2(int x, int n)
{
    //TODO: find out why DivideByPowerOf2(-33,4) = -3 instead of -2
    return x >> n;
}

DivideByPowerOf2(15,1) = 7没事。

但是DivideByPowerOf2(-33,4) = -3而不是-2。为什么？

Answer 1

在我自己寻找了一个很好的答案之后，我偶然发现了这个问题，并得到了一个有用的片段。让我向将来可能发现这一点的其他人解释一下这一点。

(x + ((x >> 31) & ((1 << n) + ~0))) >> n

正如Sotelo发布的那样，这段代码片段就是您要寻找的内容。但是，它起作用的原因是非常重要的，特别是对于你理解你的家庭作业。首先，您必须完全理解2的补码表示。这是当使用最重要位以相应的2的幂抵消整个二进制表示时。如果我们只显示32位(在大多数处理器中是标准的)，那么我们可以使用右移位(>>)将最重要的位移动到最小的位。在这样做时，您将做一个算术右移，它将在整个位级表示中复制最重要的位(如果是负的话是1)。在6位二进制表示中，这将导致

000000
111111

这样我们就可以进一步对整数进行操作来确定一些属性。首先，我们需要求2的幂，除以(在这个例子中是n)，然后将二进制移到那个位置，然后- 1，例如，我们使用3或8的幂。

(000001 << 3) -1
000111

现在我们有了这两个二进制表示，我们将把它们放在一起。

111111 & 000111 = 000111 (case 1)
000000 & 000111 = 000000 (case 2)

现在，如果x是奇数或偶数(分别为1和2)，我们可以将x相加，得到一个完全幂为2的数(如果我们除以2的幂，我们将得到一个适当的答案)。下面是一些分别为x= 8、10、-8、-12的例子。

001000 + 000000 = 001000
001010 + 000000 = 001010
now for the negatives that plague you
111000 + 000111 = 111111
110100 + 000111 = 111011

最后一步是把这些数字除以n的幂，除以8，这就是上面所说的3。

001000 >> 3 = 000001 or 1 in decimal (8/8 = 1)
001010 >> 3 = 000001 or 1 in decimal (10/8 = 1 because of truncation)
111111 >> 3 = 111111 or -1 in decimal (-8/8 = -1)
111011 >> 3 = 111111 or -1 in decimal (-12/8 = -1 because of truncation)

所以你就有了。你的第一个任务是找出它是负的还是正的，然后从与你的2 -1的能力相对应的负值中得到位。把这个加到你的x中，得到二进制的2可除数的幂。最后，将你的力量右移两次。

Answer 2

密切关注舍入行为。

• / (整数除法)总是以零为圆圈。
• 位移位是做什么的？
• 你如何才能弥补这一差异？

Answer 3

public int DivideByPowerOf2(int x, int n)
    {

        return (x + ((x >> 31) & ((1 << n) + ~0))) >> n;
    }