I was initially skeptical of your benchmarking results because of your testing methodology:
I test both of the method by sending 1 << n, n from 0 to 31 to them, and repeat for 1000000 times, and count the time separately.
When you're benchmarking code that contains conditional branches, it is generally not a good idea to use a predictable sequence of inputs, since this tends to ensure that branch prediction will be successful, mitigating something that is potentially one of the most significant costs in performance-sensitive code. Unless you're actually going to be using this function in a setting where the inputs (and thus the direction of the branches) are predictable, you run the risk of skewing the benchmark results. And even if the real-world inputs aren't purely random, you're testing here in a tight loop, which improves branch prediction even more.
To verify for myself, I used the outstanding Google Benchmark library. This automates most of the dirty work of creating a good benchmark. In my test harness, I just defined the necessary functions and prepared some arrays of randomly-generated numbers. The random number generation is done "off the clock" so it won't affect the measurement. Despite my earlier admonitions, though, it appears that your findings were valid; here are the results from my machine, using inputs randomly selected from a large array of randomly-generated values:
Benchmark Time CPU Iterations
-----------------------------------------------------------
Log2 21 ns 21 ns 29866667
Log2New 10 ns 10 ns 74666667
Log2NewUnrolled 6 ns 6 ns 112000000
(As you can see from my function names, the word you were trying to think of when composing the question is "unroll". You've unrolled (or unwound) the while loop, which attempts to gain execution speed in exchange for code size, primarily by reducing the overhead of the loop itself. In this case, you've completely unwound the loop, allowing it to be eliminated entirely. This is a very common low-level optimization, although the customary caveat is that it significantly bloats the size of the code. That is true here as well, so it rarely makes sense to go to this extreme when optimizing unless the code is going to be called in a tight loop.)
I see essentially the same thing when compiling for 64-bit. Each improvement roughly corresponds to a doubling in overall performance, which is actually pretty impressive. Although it is almost certainly possible to squeeze more speed out of your code by iterative improvements, it will become increasingly difficult to do so. The magnitude of improvement will become a lot less significant, and you'll very quickly hit up against the limitations of writing code in a compiled language, where you can't manually tweak the generated assembly.
I would also advise you to consider whether it is really necessary. The benchmarks above suggest that on a mobile Haswell processor, you can compute the base-2 logarithm of in ~6 nanoseconds. Do you really need an implementation that is faster than that? Is it really worth the time it takes to develop one, test it, and maintain it?
Well, let's suppose either that you do need something faster, or perhaps that it's worth the time simply because it's fun. One possible tack is to seek out a way to completely eliminate branches. Rather than doing the shift-and-test-and-maybe-add dance each time, we'll simply do all of the shifts and bitwise-OR the results together. Then, the final answer is obtained by doing a population count (i.e., computing the Hamming weight). The code looks like this:
unsigned int Log2Fast(unsigned int N)
{
N |= (N >> 1);
N |= (N >> 2);
N |= (N >> 4);
N |= (N >> 8);
N |= (N >> 16);
return (PopCount(N) - 1);
}
The nice thing about a population count is that there are several highly-efficient ways to do it. The accepted answer to the linked question shows one possibility, a clever bit-twiddling trick that counts in parallel, also shown on Sean Eron Anderson's Bit-Twiddling Hacks page. This is a good general-purpose implementation. If you have a processor that supports it, you can use the POPCNT instruction (available on Intel Nehalem, AMD Barcelona, and later generations). On MSVC, the __popcnt intrinsic allows you to force this instruction to be emitted.
This gets compiled to beautiful, efficient, completely branchless code:
Log2Fast PROC
mov ecx, DWORD PTR [N]
mov eax, ecx // N |= (N >> 1)
shr eax, 1
or ecx, eax
mov eax, ecx // N |= (N >> 2)
shr eax, 2
or ecx, eax
mov eax, ecx // N |= (N >> 4)
shr eax, 4
or ecx, eax
mov eax, ecx // N |= (N >> 8)
shr eax, 8
or ecx, eax
mov eax, ecx // N |= (N >> 16)
shr eax, 16
or eax, ecx
popcnt eax, eax // return (PopCount(N) - 1)
dec eax
ret 4
Log2Fast ENDP
Benchmark Time CPU Iterations
------------------------------------------------------------------
Log2 21 ns 20 ns 34461538
Log2New 10 ns 10 ns 64000000
Log2NewUnrolled 6 ns 6 ns 112000000
Log2Fast 5 ns 5 ns 89600000
Log2Fast_Intrinsic 4 ns 4 ns 179200000
Notice that the POPCNT instruction (the _Intrinsic variant shown here) is slightly faster than the hand-optimized bit-twiddling code. In fact, this single snapshot of the results is a bit of a lie. Log2Fast takes anywhere from 5–8 ns, varying slightly each time I run the benchmark. The version that uses the POPCNT instruction is consistently fast. If you can't guarantee that your target system supports this instruction, this implementation may not be any better than what you already have. It almost certainly would not be worth it except in a tight loop, when all of the required code is guaranteed to be hot in the cache. The POPCNT version, on the other hand, is actually shorter than your previous implementation, and that, combined with its lack of conditional branches, would make it a better general-case algorithm and possibly faster.
Can we do even better? Maybe. It's extremely hard to tell at this point, because our performance is already so good that the benchmark has virtually reached its limits. The performance differences we'll see will be almost exclusively due to noise. You'd say we need to improve our benchmark, but I'd say that we need to stop optimizing because we're done!
Some people have proposed an approach that uses a look-up table. The look-up table is implemented as an array, filled statically and compiled directly into the executable, with the intention of saving us from having to do expensive computations at runtime, since we can just index into the array and retrieve the precomputed value. The same solution also appears on the previously-linked Bit Twiddling Hacks page. What you'll notice, though, is that the look-up table is only being used to do the population count. Specifically, the look-up table contains a DeBruijn sequence, which is a well-known way to speed up various bit-counting operations, including finding the MSB, finding the LSB, and, of course, finding the total number of set bits.
We cannot reasonably use a look-up table for the shifting operations, because it would be ginormous. And, unfortunately, the population-count code we have is already so fast that it cannot be sped up with a look-up table. This is actually so interesting (and counter-intuitive) that it warrants a bit of further commentary. I tested this extensively a while back when I needed to find the position of the least-significant set bit (as part of an optimized implementation for strlen). I assumed that a look-up table would be the fastest solution, but it wasn't. Even as far back as a Pentium III, it turned out to be faster (or at least equally as fast) to simply compute the value at runtime. Sometimes, modern processors are like this—they are so fast, that it can be faster to recompute something than to store it and/or look it up. It is also a good demonstration of the fact that (micro-)optimization is often counter-intuitive, and can only be done correctly with the aid of a good benchmark test case!
I know I already said that we're pushing the limits of performance and that the code is already fast enough, but maybe there is a way to push it just a little bit faster? Or at least, maybe we can gain some style points for a truly efficient algorithm!
Let's stop and think for a moment about what we're actually trying to do. What is the log base-2 of a number? Well, it is the binary logarithm—the power to which you must raise 2 in order to obtain that number. The lightbulb might have already flashed on here, after seeing that word "binary". Computers work in binary. More specifically, numbers are stored using a binary representation. That's why your bit-shifting algorithm worked. Since binary is fundamentally based on log2, it turns out that the position of the most-significant set bit is the same as the binary logarithm of the represented value. For example, consider the number 21658123. Its binary logarithm is 24, and its binary representation is:
0001 0100 1010 0111 1010 0000 1011
↑ ↑ ↑
| └————— bit 24 |
bit 31 bit 0
The index of the first set bit, when searching from most-significant bit (MSB) to least-significant bit (LSB), is 24—exactly the same as the binary logarithm. This hints at an exceptionally simple algorithm (at least conceptually): scan through the binary representation of the number looking for the most significant set bit! As luck would have it, there is an instruction on x86 to do precisely what we want to do, and it's been available since the 386 way back in 1986. That is the BSR instruction (Bit Scan Reverse), usable in MSVC via the _BitScanReverse intrinsic and on Gnu compilers (i.e., GCC and Clang) via the __builtin_clz intrinsic (although you'll need to XOR the result with 32). And even if you're not targeting the x86, the intrinsic will likely still work for you, causing the compiler to use an architecture-provided instruction if available, or emit code to generate the equivalent result.
Here's our updated function:
unsigned int Log2_ViaBSR(unsigned int value)
{
unsigned long result;
_BitScanReverse(&result, static_cast<unsigned long>(value));
return result;
}
(Yes, code that should be a single line looks a little bit bloated here because MSVC's _BitScanReverse intrinsic works only with DWORD values, which is a typedef for unsigned long, not unsigned int, so although on Windows they are both 32-bit types, they are nevertheless different types according to the language standard, so you need to declare and use an additional temporary for the output, instead of simply reusing the input parameter. Fortunately, this does not affect the object code generated by the compiler. Note, also, that the intrinsic returns a Boolean value indicating whether it was successful. This allows you to handle the case where the input is 0 and the result is undefined—see "caveats" below.)
And the updated leaderboard:
Benchmark Time CPU Iterations
------------------------------------------------------------------
Log2 22 ns 21 ns 32000000
Log2New 10 ns 10 ns 64000000
Log2NewUnrolled 6 ns 6 ns 112000000
Log2Fast 7 ns 6 ns 89600000
Log2Fast_Intrinsic 4 ns 4 ns 186666667
Log2_ViaBSR 2 ns 2 ns 298666667
Stop and think about this for a second. We went from an O(log n) algorithm to what is effectively an O(1) algorithm, just by thinking about the problem in a different way, and figuring out how we can leverage the computer's internal binary representation to our advantage. It reminds me of a lesson straight out of Michael Abrash's Zen of Assembly Language. We now have the most efficient algorithm and have earned those style points!
Now, there are a couple of caveats. First off, log2(0) is mathematically undefined, so you have to decide how you want to handle that. I've simply ignored it in all of the code I've written, making it undefined there as well. The BSR instruction and its corresponding intrinsics take the same tack, formally defining the result as "undefined" when the input is 0. And although there is actually a lot more that I could say about this (including possible workarounds for "undefined" inputs, inefficient code generation when this intrinsic is used in MSVC, the similar LZCNT instruction introduced on Intel Haswell, etc.), I probably shouldn't make this answer any longer. Instead, I'll refer you to Peter Cordes's recent answer on the subject, and my comments below it.
