How to turn a division into a bitwise shift when power of two?

Question

I have the following division that I need to do often:

int index = pos / 64;

Division can be expensive in the cpu level. I am hoping there is a way to do that with bitwise shift. I would also like to understand how you can go from division to shift, in other words, I don't want to just memorize the bitwise expression.

Answer 1

int index = pos >> 6 will do it, but this is unnecessary. Any reasonable compiler will do this sort of thing for you. Certainly the Sun/Oracle compiler will.

The general rule is that i/(2^n) can be implemented with i >> n. Similarly i*(2^n) is i << n.

You need to be concerned with negative number representation if i is signed. E.g. twos-complement produces reasonable results (if right shift is arithmetic--sign bit copied). Signed magnitude does not.

Answer 2

The compiler will implement it for you in the most efficient way, as long you understand what you need and ask the compiler to do exactly that. If shift is the most efficient way in this case, the compiler will use shift.

Keep in mind though that if you are performing signed division (i.e pos is signed), then it cannot be fully implemented by a shift alone. Shift by itself will generate invalid results for negative values of pos. If the compiler decides to use shifts for this operations, it will also have to perform some post-shift corrections on the intermediate result to make it agree with the requirements of the language specification.

For this reason, if you are really looking for maximum possible efficiency of your division operations, you have to remember not to use signed types thoughtlessly. Prefer to use unsigned types whenever possible, and use signed types only when you have to.

P.S. AFAIK, Java implements Euclidean division, meaning that the above remarks do not apply to Java. Euclidean division is performed correctly by a shift on a negative divisor in 2's-complement representation. The above remarks would apply to C/C++.