Find the least exponent of power of twos in a positive integer.

49 Views Asked by At

Is there a simple formula to find the index or the least exponent when a positive integer is built on power of twos? (Such as in binary).

For example say I chose a random number: $51840$, which is: $1100101010000000_2$ and $2^{15} + 2^{14} + 2^{11} + 2^9 + 2^\boxed{\color{red}7}$.

So basically what I need is some function $f$, that will return $x$ where $x\in\mathbb{N^0}$, in above example: $f(51840) = 7$.

I remember seeing a function somewhere that did this, but I dont remember where.

1

There are 1 best solutions below

0
On BEST ANSWER

Well you have defined the function you want. You've also described a way to calculate its value: write the number in binary and count the number of trailing $0$s. Equivalently, divide by $2$ as many times as you can - the number of times is the value of your function. That's an easy computer program in most languages.

I don't think there's a name or a "simple formula" for it.

Edit. This function does have a name: it's the $2$-adic valuation. See https://en.wikipedia.org/wiki/P-adic_order .