CODEWITHSUNDEEP
calgorithmmath
Vince.Wu
Vince.Wu

Reputation: 890

Is there any fast algorithm to compute log2 for numbers that are all power of 2?

Is there any fast algorithm to compute log2 for numbers that are all power of 2,eg:

log2(1), log2(2), log2(4), log2(1024), log2(4096)...

I'm considering using it to implement bit set iteration.

Upvotes: 5

Views: 2415

Answers (2)

DrV
DrV

Reputation: 23510

Three more theoretically possibly efficient algorithms in addition to the ones already given or linked. n is the number of bits, N = 2^n:

  1. Big LUT: one lookup
  2. Simple binary search: log2(n) comparisons
  3. LUT[N % k] with k-position LUT: one modulo, one lookup (k=37 for 32-bit and 67 for 64-bit numbers)

In practice, #1 is great with small n, #2 may be fastest on certain hardware (something without fast multiply), but the code looks ugly. #3 probably never beats DeBruijn on a real machine, but it has fewer operations.

Upvotes: 3

Bryan Chen
Bryan Chen

Reputation: 46598

assuming you know the number must be power of 2, so in binary, it is 1 following with n 0 where n is the number you are looking for.

if you are using gcc or clang, you can use builtin function

— Built-in Function: int __builtin_ctz (unsigned int x)

Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.

for pure C implementation, it is already answered

Finding trailing 0s in a binary number

Upvotes: 21

Related Questions