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. 

One easy way would be to find $\gcd(2^{\lfloor \log_2 n \rfloor}, n)$, which is quite fast through the Euclidean algorithm. This runs in time about $\log n$.
Of course, that's also as long as it would take to perform an efficient binary search.
