8

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?

Cheok Yan Cheng
  • 47,586
  • 132
  • 466
  • 875

6 Answers6

18

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.

ergosys
  • 47,835
  • 5
  • 49
  • 70
  • 2
    +1 for noting that, if you want to divide by 2, you might just try the division operator and see how well that works. – President James K. Polk Jan 27 '10 at 01:18
  • 2
    +1 - thanks also for highlighting that sub-optimizations very often don't beat the work done by the compiler, and the "naive" option is often efficient and correct on basic stuff like this. – Matt Jan 27 '10 at 01:18
  • Any negative odd number will result in (as with any positive odd number) n/2 rouned towards -inf. Just so happens that for n == -1, that is -1. – Vatine Jan 27 '10 at 07:36
12

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

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • This really is the best answer here. This kind of code change is at least the third step in the process: the first being profiling of the code to determine that this is a significant bottleneck, and the second being aware of what the resulting bytecode/JIT is and recognizing that to be suboptimal. – corsiKa Nov 26 '13 at 15:44
4

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;
Anon.
  • 58,739
  • 8
  • 81
  • 86
  • +1: but why do you have to check `n & 1 >0`. A check for `n < 0` alone is sufficient This works:`int result=x>>1; if (x>=0){ return result; } else { return ++result;}` – eagertoLearn Jan 02 '14 at 20:09
  • @eagertoLearn: Only odd negative integers give the undesired result. – Zantier Jan 07 '15 at 16:31
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?

Community
  • 1
  • 1
Paul Wagland
  • 27,756
  • 10
  • 52
  • 74
4

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);`
nik3daz
  • 111
  • 1
  • 7
0

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++;
Samuel Carrijo
  • 17,449
  • 12
  • 49
  • 59