c# - 使用位移除以 2 的幂

Question

我有以下任务:

Compute x/(2^n), for 0 <= n <= 30 using bit shifting.

Requirement: Round toward zero.

Examples:

divpwr2(15,1) = 7
divpwr2(-33,4) = -2

Legal operators: ! ~ & ^ | + << >>

Maximum number of operators: 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

这样我们就可以进一步对整数进行操作以确定某些属性。首先，我们需要找到我们要除以(在本例中为 n)的 2 的幂，并将二进制移动到该位置，然后减去 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 可整除数的幂。然后最后将你的 2 的幂右移。