使用位移除以2的幂 [英] Dividing by power of 2 using bit shifting

问题描述

我有以下任务:

使用移位将x/(2^n)用于0 <= n <= 30.

要求:向零舍入.

示例:

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

法律运营商:! ~ & ^ | + << >>

最大操作员数:15

这是我到目前为止所得到的:

Here is what I've got so far:

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.为什么?

But DivideByPowerOf2(-33,4) = -3 instead of -2. Why?

推荐答案

我自己寻找了一个很好的答案后，偶然发现了这个问题，并且能够找到一个有效的代码段.让我向将来可能会发现的其他人解释一下.

After looking for a good answer myself, I stumbled across this and was able to get a working snippet. Let me help explain this to others that may find this in the future.

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

此代码段就是Sotelo发布的所要查找的内容.尽管它起作用的原因非常重要，特别是对于您了解作业而言.首先，您必须完全理解2的补码表示形式.这是当最高有效位用于将整个二进制表示偏移对应的2的幂时. 如果仅映像32位(大多数处理器中为标准映像)，则可以使用右移(>>)将最高有效位移动到最低有效位.这样，您将进行算术右移，它将在整个位级别表示中复制该最高有效位(如果为负，则为1).在6位二进制表示形式中，这将导致两者之一

This snippet of code is what you are looking for as posted by Sotelo. The reason it works though is very important especially for you to understand your homework. First you must understand fully 2's complement representation. This is when the most significant bit is used to offset the entire binary representation by the corresponding power of 2. If we image just 32 bits (standard in most processors) then we can use a right shift (>>) to move the most significant bit to the least significant bit. In doing so you will do an arithmetic right shift which will copy that most significant bit (a 1 if it is negative) throughout the entire bit level representation. In a 6 bit binary representation this would result in either

000000
111111

然后，这允许我们进一步对整数进行操作以确定某些属性.首先，我们需要找到2的幂，然后将其除以(在本例中为n)，然后将二进制数移至该位置，然后减负1.例如，让我们使用3或8的幂.

This then allows us to further operate on the integer to determine some properties. First we need to find the power of 2 we are going to divide by (in this case n) and shift a binary on to that position, then minus 1. For example let's use power of 3 or 8.

(000001 << 3) -1
000111

现在我们已经有了这两种二进制表示形式，我们将和它们在一起

now that we have both of these binary representations we will and them together

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

现在给定x为奇数或偶数(分别为情况1和情况2)，我们可以将x加到上面，得到一个数字，该数字是2的完美幂(如果我们除以2的幂，我们将得到一个适当的乘方)回答).以下是x分别为8、10，-8，-12的几个示例.

now given that x is odd or even (case 1 and case 2 respectively) we can add x to this and get a number which is a perfect power of 2 (if we divide by a power of two we will get a proper answer). Below is a few examples with x = 8, 10, -8, -12 respectively.

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

现在，最后一步是将这些数字除以n的幂.如要除以8，则如上所述就是3.

Now the final step is to divide these numbers by our power of n. For dividing by 8 this is then 3 as stated above.

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的幂右移.

So there you have it. You first task is to find if it is negative or positive, then get the bit from the negative that corresponds to your power of 2 -1. Add this to your x to get your power of 2 divisible number in binary. Then lastly divide you a right shift of your power of two.

这篇关于使用位移除以2的幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！