Formula to compute binary trailing zeroes of an integer

Question

I'm looking for a (simple) formula $t: \mathbb{N} \rightarrow \mathbb{N}$ to compute the number of trailing zeroes in the binary representation of a given $n \in \mathbb{N}$.

Like so:
$t(1) = t([1]_2) = 0$
$t(2) = t([10]_2) = 1$
$t(3) = t([11]_2) = 0$
$t(4) = t([100]_2) = 2$
etc.

I once found a rather complex formula back in 2016, that actually works, but is very clunky:
$t(n) = \sum_{k=1}^\infty cos( \frac{1}{2^k} \pi n) \prod_{j=1}^k cos( \frac{1}{2^j} \pi n)$
The basic idea behind this one is to sum cosines, which become $1$ at some $2^k$ and $0$ otherwise. It works, is provable by induction and I have worked with it, like e.g. here (sorry for IEEE paywall, it is just an example and not that much of importance).

However, I am still wondering, if there isn't any better or more simple way to describe $t(n)$, as the above formula is really hard to use. It also relies on non-integer functions (cosine), despite $t(n)$ being an $\mathbb{N} \rightarrow \mathbb{N}$ function.

Any ideas? Thanks in advance!

Answer 1

The number of trialing zeros in binary notation is the highest power of $2$ that divides the number in decimal notation.

$t(n)=\displaystyle \sum_{k=1}^\infty \left( 1-\left\lceil\left\{\frac{n}{2^k}\right\}\right\rceil\right)$ satisfies the above condition (where {} denotes the fractional part).

If $k$ is the highest power of $2$ that divides $n$, then the first $k$ terms of $t(n)$ is $1$ while the rest of the terms are $0$ so the formula for $t(n)$ gives the number of trialing zeros in binary notation.

Answer 2

What you are trying to compute is $\nu_2(x)$, the $2$-adic valuation of $x$, i.e. the highest exponent $\nu_2(x)$ such that $2^{\nu_2(x)}$ divides $x$ (see here).

If you like a fanciful formula you can get this one:

$$\nu_2(x) = \log_2 \left[x - \sum_{k=0}^{\lfloor \log_2{x} \rfloor}\left(\left\lfloor\frac{2x-1+2^{k+1}}{2^{k+2}}\right\rfloor - \left\lfloor\frac{2x-1+2^{k+2}}{2^{k+3}}\right\rfloor - \left\lfloor \frac{x}{2^{k+2}} \right\rfloor\right)2^k \right] + \frac{1+(-1)^x}{2}$$

For an explanation see here.