Dividing by power of 2 using bit shifting

I've got the following task:开发者_开发技巧

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

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 is ok.

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

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

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)

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

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)

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.

Pay close attention to the rounding behavior.

• / (integer divide) always rounds toward zero.
• What does bit shifting do?
• How can you compensate for this difference?

public int DivideByPowerOf2(int x, int n)
    {

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

Negative numbers work out to be one off in the binary representation due to their two's complement representation. Perhaps reading about two's complement will help.