Geek Answers Handbook

Isolate the leftmost 1-bit

I was looking for bit-bit allocation in binary format:

And I got this solution:

y = x & (-x)

So:

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

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

How can I develop a solution of mine to find the leftmost bit?

Examples

:

10 1 11100

0 1 000100

+6
source share
2 answers

There is no similar O (1) bitwise trick to find the value of a number. Many microprocessor sets contain special instructions for "counting leading zeros." There is no operator in the C language family that has given JavaScript its bit-by-bit functionality.

The only alternative to O (1) is to use Math.floor( Math.log( n ) / Math.LN2 ) Quick Test

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

gives i == 31 as a result, due to the << operator using 32-bit arithmetic, signed by two additions.

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

Code for 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 them, you need to shift left by the result to get the "leftmost 1-bit", not the index.

EDIT: Note. The log implementation returns -Infinity for zero, while the mag function returns 0 , which matches its result for 1 . If you want to take into account the possibility of the absence of a left 1-bit existing one, it is better to make it a special case.

+4
source

I do not think that Math.floor( Math.log( n ) / Math.LN2 ) is O (1) due to Math.log not a fundamental operation.

So, the following theorem says that you cannot get the leftmost 1-bit: "A function that translates words into words can be implemented by adding, subtracting and / or verbally, and not commands, if and only if each bit of the result depends only the bits in and to the right of each input operand. "

This theorem is given on page 13 of Hacker Delight (Henry S. Warren, Jr.).

+1
source

More articles:


All Articles