The most EFFIECIENT algorithm to find how many times a number can be divided by 2 before it reaches 1 [Note: if possible in O(1) time]

Question

I tried using log but it is consuming more time than the iterative version for finding the answer. The number is integer.

Using log:-
int ans = (log(x)/log(2));

Iterative version:-
int temp;
while(x)
{
    temp = temp/2;
    count++;
}
count--;

Real life efficient (see existing answers) or asymptotically efficient (see other existing answers)? — harold, Sep 22 '16 at 19:18
Is your number size and type known (32-bit/64-bit integer, 32-bit float, ...) ? I can only guess it's an integer since it "reaches 1" when successively dividing it by 2. — Nelfeal, Sep 22 '16 at 19:20
@harold From what is shown, the code doesn't test for anything. The question implies that a number eventually reaches 1 when successively divided by 2. A floating-point number doesn't work that way. An integer does. What's your point ? — Nelfeal, Sep 22 '16 at 19:36
@Nelxiost it doesn't rely on reaching 1 at all, though it would anyway since this is definitely the integer version so the only way to get 0 is by getting to 1 first. It relies on reaching 0, which also works for floats, but then this ends up being wrong anyway so it cannot be the float version. — harold, Sep 22 '16 at 19:40
http://stackoverflow.com/questions/9117793/bitwise-most-significant-set-bit — stark, Sep 22 '16 at 21:24
@Nelxiost If number is integer it will reach 1 Sorry for not telling you the datatype. I have edited it now — Rahul Sonwanshi, Sep 23 '16 at 08:50

score 1 · Accepted Answer · answered Sep 23 '16 at 07:31

Basic Integer datatype

for integers on x86 architecture there is a single O(1) instruction for this:
- BSR bit scan reverse
that returns position of MSB set bit. So you do not need to do the iterative O(log(n)) dividing, shifting or bin-search. To make sure the sign (2'os complement) does not mess this up for negative numbers use abs value for this.
bigints

For these you need to check the MSW non zero WORD. and use #1 on it. This is O(log(n)). Where n is the number you are testing.
floating point

These are usually very simple O(1) as you just extract exponent which tells you the position of MSB set bit directly.

Also log2 is directly implemented by FPU HW for basic floating datatypes on most architectures but they will not return integer style result ...

1 Answers1