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

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 2

@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.

Answer 3

I got bored one day and profiled divides vs shifts for power of 2 stuff; thought I'd post it here for anyone interested.

On HotSpot VM 1.6 on Windows, using j /= 4 across -100000000 to 100000000 ran in about 12 seconds while using j = (j >= 0) ? j >> 2 : ~(~j+1 >> 2) + 1; ran in just 2.5s.

OpenJDK VM 1.6 on Linux got 5.5s for divides and 1.5s for shifts.

This would suggest that the JIT compiler doesn't really do anything fancy for power of 2 division.

GCC managed to optimize the division so that it was faster than the flips and shifts.

~(~j+1 >> 2) + 1 uses twos complement to flip the number positive, shift and flip it back.

long j = 0;
for (long i = -100000000; i < 100000000; i++) {
    j = i;
    j /= 4;
}
System.out.println(j);`

vs

long j = 0;
for (long i = -100000000; i < 100000000; i++) {
    j = i;
    j = (j >= 0) ? j >> 2 : ~(~j+1 >> 2) + 1;
}
System.out.println(j);`