5

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.

Vince.Wu
  • 870
  • 1
  • 10
  • 17
  • 2
    Yes but the answer wouldn't be the same as if you asked for a fast way *in practice*, and the last sentence of your post suggests you might want that. Could you clarify what you're doing? Is this for real-life programming? If so, could you tag a language? – harold Jun 20 '14 at 13:33
  • 2
    Have a look at https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious – Marco13 Jun 20 '14 at 13:34
  • @harold Sorry, I forgot, I'm using C language, and as I've said above, I'm using it to implement a bit set iteration function. – Vince.Wu Jun 20 '14 at 13:37
  • I'm sure that has been covered before, I can't seem to find a *good* duplicate though. You could try searching stackoverflow yourself and see if you find anything you like. – harold Jun 20 '14 at 13:41
  • 1
    Equivalent to finding first set bit. Take a look at http://en.wikipedia.org/wiki/Find_first_set – SomeWittyUsername Jun 20 '14 at 13:47
  • @harold Yes, I've searched for this problem, and some formal questions look quite the same, but the difference is that the input are numbers that are all power of two in my case. – Vince.Wu Jun 20 '14 at 13:48
  • @user486005 there is already a way to get log2 of a power of 2 on bithacks: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog read the `// OR (IF YOU KNOW v IS A POWER OF 2)` part below. There is a MultiplyDeBruijnBitPosition2 version for powers of 2 too – phuclv Jun 20 '14 at 14:34
  • Here's a link to the method @LưuVĩnhPhúc mentions: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn - One multiply, one cast, one bit-shift, and an array lookup. – pjs Jun 20 '14 at 14:38
  • Possible duplicate of [Fastest way of computing the power that a "power of 2" number used?](https://stackoverflow.com/questions/21438631/fastest-way-of-computing-the-power-that-a-power-of-2-number-used) – phuclv Nov 02 '17 at 12:38

2 Answers2

19

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

Community
  • 1
  • 1
Bryan Chen
  • 45,816
  • 18
  • 112
  • 143
  • Any material about the algorithm used in __builtin_ctz? And for numbers that are power of 2, is there any optimization that can be performed? – Vince.Wu Jun 20 '14 at 15:47
  • @user486005 `__builtin_ctz` maps directly to the `bsf` (bit scan forward) instruction. So it is done very efficiently in hardware. – Mysticial Jun 20 '14 at 17:24
1

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.

DrV
  • 22,637
  • 7
  • 60
  • 72