Binary logarithm in O(1) time (operating on registers x86 or SIMD) without shifting?

Question

I wanted to see if there is a method for finding the binary log of a number. Say you have the number 4 then the power to which you raise two to get four is 2.

I know this is possible with shifting and counting but that uses O(N) operations. Is there some way to get O(1) for any n where x = 2^n?

I want to find n here knowing x in one operation or O(1).

Answer 1

As you've specified x86, it sounds like you want the BSR (bit-scan reverse) opcode, which reports the position of the most-significant set bit.

[FYI: big-O notation refers to asymptotic complexity (i.e. as N -> infinity); it doesn't make much sense if N has a finite limit (32 or 64 in this case).]