Right Shift to Perform Divide by 2 On -1

Question

I know that I can perform divide by 2 using right shift.

For simplicity, take a 4 bit number system

-1 - 1111
-2 - 1110
-3 - 1101
-4 - 1100
-5 - 1011
-6 - 1010
-7 - 1001
-8 - 1000
7  - 0111
6  - 0110
5  - 0101
4  - 0100
3  - 0011
2  - 0010
1  - 0001
0  - 0000

If I try to perform

6 / 2 = 0110 >> 1 = 0011 = 3
-6/ 2 = 1010 >> 1 = 1101 = -3

Is valid for both +ve and -ve number

However, when come to 1

1 / 2 = 0001 >> 1 = 0000 = 0
-1/ 2 = 1111 >> 1 = 1111 = -1

Seems like there is a special case in -1, as right shift then to move it to negative infinity.

Currently, I need to put a special if check for this, as I am expecting -1 / 2 = 0.

I was wondering how do you guy handle this exception in your code? You guy put an if check?

Answer 1

In the odd case, both operations result in a floor operation in the result.

• 3/2 -> floor(1.5) => 1
• -3/2 -> floor(-1.5) => -2

You could put a check, something like\

if ( isOdd(number) && isNegative(number) )
   result++;

Answer 2

If you right-shift to divide by two, you always end up "rounding" down - towards zero if positive, away from it if negative.

If this is not what you want, you can correct for it:

if (n & 1 > 0 && n < 0)
    result += 1;

Answer 3

Any negative odd number won't work. However to answer your question, if you know you can have negative numbers, just divide by 2. This is turned into a shift with a fixup by the jit/compiler.

Answer 4

I hate to say it, but I don't handle this in my code, since I don't use bit shifting for multiplication or division. This smells to me of a premature optimisation.

Why do you think that you need to do division with bit shifting rather than the more readable x / 2?

Answer 5

@Anon is technically correct.

However, it is best practice to use the / operator for division, and leave micro-optimization to the JIT compiler. The JIT compiler is capable of optimizing divisions by constants as shift/add sequences ... when this is an optimal thing to do for the execution platform.

Doing this kind of thing is (probably) a premature optimization, and it may be an anti-optimization if your code needs to run fast on multiple Java platforms.