Bit-length function that returns msb '1' and lsb '1'

51 Views Asked by At

I need a function that can return the length from the most significant 'on'-bit to the least significant 'on'-bit. How would you go about making such an function? Im thinking of something in the lines of subtracting some value $x$ from the standard bit-length function:

$BL(n)=1+\lfloor log_2(n)\rfloor$

or

$BL(n)=\lceil log_2(n+1)\rceil$

so the function in question is:

$F(n) = BL(n) - x$

what is $x$ here, is it has something to do with pow2?

I provide a table that should show what values to expect:

n  binary    F(n)
0  00000     0
1  00001     1
2  00010     1
3  00011     2
4  00100     1
5  00101     3
6  00110     2
7  00111     3

The sequence $0,1,1,2,1,3,2,3,1,4,3,4,2,4,3,4,1...$ does not match in the OEIS.

1

There are 1 best solutions below

2
On BEST ANSWER

It has to do with the 2-adic valutation of $n$, see here. Let $$ v_2(n) = k \text{ if } n = 2^km \text{ with $m$ odd.} $$

Then $$ F(n) = 1 + \log_2 n - v_2(n). $$