help needed-bitwise shift

[hooshdar3]

Hello.
I want to find a way to find the log_2 of a number that is supposedly a power of 2 using bitwise shift to improve the performance

[rich1]

http://stackoverflow.com/questions/141525/absolute-beginners-guide-to-bit-shifting

[Smac89]

Remember that the log_n of any value is equivalent to the number of times that value can be divided by n before it becomes 1. Or equivalently, how many times can we multiply n by itself before we get value.

So log₂ of 14 is:

14 / 2 <-- 1
7 / 2 <-- 2
3 / 2 <-- 3
1
= 3 (~3.8)

With bitwise shift, this is equivalent to right bitshift (divides by (2 ^ value specified))

log2 of 14 is:
[1110 = 2 ^ 3 + 2 ^ 2 + 2 ^ 1 + 2 ^ 0] 14 >> 1 // means 14 / (2 ^ 1) <-- 1
[111 = 2 ^ 2 + 2 ^ 1 + 2 ^ 0] 7 >> 1 // means 7 / (2 ^ 1) <-- 2
[11 = 2 ^ 1 + 2 ^ 0] 3 >> 1 // means 3 / (2 ^ 1) <-- 3
[1 = 2 ^ 0]
= 3

[Duthomhas]

What you want is a common calculation called "bit scan reverse". See this for more info and links.
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/introsort/#countdown

[hooshdar3]

How can I turn 16 to zero?
for example I have numbers from 0 to 100 and four 25-numbers-wide buckets
e.g I want 16 to fall in the range 0 to 25

[Smac89]

What do you mean 16 to fall in the range 0-25? You want to place 16 inside one of the buckets?

[hooshdar3]

Yes
and 25 within 25-49

[Duthomhas]

Are you doing a bucket sort now?

[hooshdar3]

Not now, but I want to
and I should use the shift operator, since it is faster than division

[Duthomhas]

You should not assume you can do a better job optimizing your code than your compiler can. (Not without first profiling it.)