Fastest way to compute log_2(n) where n is of form 2^k?

Say I'm given n=32. I want to know what log_2(n) is. In th开发者_开发问答is case, log_2(32) = 5.

What is the fastest way in general to compute the log of a 2^k number?

I.e. Given n = 2^k. log_2(n) = b. Find b.

Bitwise operations are permitted.

This page gives a half-dozen different ways to do that in C; it should be trivial to change them to C#. Try them all, see which is fastest for you.

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

However, I note that those techniques are designed to work for all 32 bit integers. If you can guarantee that the input is always a power of two between 1 and 2^31 then you can probably do better with a lookup table. I submit the following; I have not performance tested it, but I see no reason why it oughtn't to be pretty quick:

static int[] powers = new[] {0, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 
                        30, 28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 
                        31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 
                        20, 8, 19, 18};

static int Log2OfAPower(int x)
{
    return powers[((uint)x) % 37]
} 

The solution relies upon the fact that the first 32 powers of two each have a different remainder when divided by 37.

If you need it to work on longs then use 67 as the modulus; I leave you to work out the correct values for the array.

Commenter LukeH correctly points out that it is bizarre to have a function that purportedly takes the log of a negative number (1<<31 is a negative signed integer.) The method could be modified to take a uint, or it could be made to throw an exception or assertion if given a number that doesn't meet the requirements of the method. Which is the right thing to do is not given; the question is somewhat vague as to the exact data type that is being processed here.

CHALLENGE:

Hypothesis: The first n powers of two each have a different modulus when divided by p, where p is the smallest prime number that is larger than n.

If the hypothesis is true then prove it. If the hypothesis is false then provide a counter-example that demonstrates its falsity.

I think that if you guarantee that n will be a power of 2, a quick way to find b would be by converting n to a binary string and finding the index of 1. Special consideration for case when n = 0

using System.Linq;
...
var binaryStringReversed = Convert.ToString(value, 2).Reverse();
var b = binaryStringReversed.IndexOf("1");

EDIT:

var b = Convert.ToString(value, 2).Length - 1;