How to find the highest power of a prime dividing an integer quickly I am working on a problem which requires me to compute the highest power of $2$ diving an integer. i.e I am looking for a function $f(n)$ such that $f(2^m \times (2k+1))=m $ where $(m,k) \in \mathbb{Z^+}$
I am doubtful if a useful closed form exists for $f(n)$, in which case I will be more than happy to get a recursive formula /efficient algorithm (without having to exhaust all the possibilities or binary search) as an answer. 
Any hints or directions are appreciated. 

HINT.- Here a criterium of divisibility by $16$ for a number of more than four digits (the proof is left as an exercise).
If $n$ is the integer $n= a_na_{n-1}…..a_5\cdot 10^4 +a_4a_3a_2a_1$ then
$$16|n\iff a_1-6a_2+4a_3+8a_4\equiv 0\space (mod\space 16)$$
Hence you can successively calculate $\frac{n}{16}=n_1$, $\frac{n_1}{16}=n_2$,…,$\frac{n_{k-1}}{16}=n_k$ 
You stop when $n_k$ is not divisible by $16$. 
So you have $n$ is divisible by $16^{k-1}=2^{4(k-1)}$ or $2^{4k-3}$ or $2^{4k-2}$ or $2^{4k-1}$ according to $n_k$ be odd or exactly divisible by $2,4$ or $8$ respectively.
It is true this way  is applicable for $n$ not very large.....
