How to turn a division into a bitwise shift when power of two?
algorithm, bit-manipulation, bitwise-operators, java
Solution
`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.
Problem
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.