Isolate the leftmost 1-bit

Question

I was searching about isolating the Right-most bit stuff in binary :

And I got this solution :

y = x & (-x)

so :

    10111100  (x)
&   01000100  (-x)
    --------
    00000100

But now , I want to find the magnitude of a number by finding the left most digit ( not the sign though...)

How can I elaborate the solution of mine to find the most left-bit ?

examples :

10111100

01000100

Answer 1

There's no similar O(1) bitwise trick to find the magnitude of a number. Many microprocessor instruction sets include a special instruction to "count leading zeroes." There is no such operator in the C language family which gave JavaScript its bitwise functionality.

The only O(1) alternative is to use Math.floor( Math.log( n ) / Math.LN2 ) A quick trial of

for ( var i = 0; i == Math.floor( Math.log( 1<<i ) / Math.LN2 ); ++ i ) ;

gives i == 31 as the result, due to the << operator using 32-bit two's complement signed arithmetic.

If you want to be a purist, you can repeatedly right-shift by one, which is O( log n ), or you can repeatedly right-shift by 16 >> i, for i from 0 to 4, rejecting shifts when the result is zero and otherwise accumulating 16 >> i. That is O(log log N) where N is the maximum possible value for n, which means constant time, but in all probability slower than Math.log.

Code for the O( log log N ) algo:

var mag = function( n ) {
     var acc = 0;
     for ( var i = 16; i; i >>= 1 ) {
         if ( n >> i ) {
             n >>= i;
             acc += i;
         }
     }
     return acc;
};

Of course, for any of these, you have to left-shift one by the result to obtain the "leftmost 1-bit" rather than an index.

EDIT: Note, the log based implementation returns -Infinity for zero, whereas the mag function returns 0, which is the same as its result for 1. If you want to account for the possibility of no leftmost 1-bit existing, better to make it a special case.

Answer 2

I don't think that Math.floor( Math.log( n ) / Math.LN2 ) is O(1) due to Math.log isn't a fundamental operation.

So, following theorem say that you can't get the leftmost 1-bit: "A function mapping words to words can be implemented with word-parallel add, subtract, and, or, and not instructions if and only if each bit of the result depends only on bits at and to the right of each input operand."

This theorem is on page 13 of "Hacker's delight" (Henry S. Warren, Jr.) book.