CODEWITHSUNDEEP
c#mathbit-manipulation
Michael Ryan
Michael Ryan

Reputation: 489

How to determine the number of right bit-shifts needed for a power of two value?

I have a function that receives a power of two value.

I need to convert it to an enum range (0, 1, 2, 3, and so on), and then shift it back to the power of two range.

 0         1
 1         2
 2         4
 3         8
 4        16
 5        32
 6        64
 7       128
 8       256
 9       512
10      1024
... and so on.

If my function receives a value of 1024, I need to convert it to 10. What is the best way to do this in C#? Should I just keep dividing by 2 in a loop and count the iterations?

I know I can put it back with (1 << 10).

Upvotes: 0

Views: 942

Answers (3)

David Schwartz
David Schwartz

Reputation: 182829

This is the probably fastest algorithm when your CPU doesn't have a bit scan instruction or you can't access that instruction:

unsigned int v;  // find the number of trailing zeros in 32-bit v 
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

See this paper if you want to know how it works, basically, it's just a perfect hash.

Upvotes: 2

Andre Loker
Andre Loker

Reputation: 8408

Just use the logarithm of base 2:

Math.Log(/* your number */, 2)

For example, Math.Log(1024, 2) returns 10.

Update:

Here's a rather robust version that checks if the number passed in is a power of two:

public static int Log2(uint number)
{
  var isPowerOfTwo = number > 0 && (number & (number - 1)) == 0;
  if (!isPowerOfTwo)
  {
    throw new ArgumentException("Not a power of two", "number");
  }

  return (int)Math.Log(number, 2);
}

The check for number being a power of two is taken from http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2

There are more tricks to find log2 of an integer on that page, starting here: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

Upvotes: 5

David Schwartz
David Schwartz

Reputation: 182829

Use _BitScanForward. It does exactly this.

Upvotes: 0

Related Questions