What’s the quickest way to compute log2 of an integer in C#?

by

Slight improvement to Guffa’s answer… Since the amount you are adding to the result is always a power of two using bit operations can produce slight improvement on some architectures. Also since our context is bit patterns it is slightly more readable to use hexadecimal. In this case it is useful to shift the arithmetic by a power of 2.

int bits = 0;

if (n > 0xffff) {
  n >>= 16;
  bits = 0x10;
}

if (n > 0xff) {
  n >>= 8;
  bits |= 0x8;
}

if (n > 0xf) {
  n >>= 4;
  bits |= 0x4;
}

if (n > 0x3) {
  n >>= 2;
  bits |= 0x2;
}

if (n > 0x1) {
  bits |= 0x1;
}

Further a check for n==0 should be added since the above will yield a result of 0 and Log(0) is undefined (regardless of base).

In ARM assembly this algorithm produces very compact code as the branch after comparison can be eliminated with conditional instructions which avoids pipeline flushing. For Example:

if (n > 0xff) {
   n >>= 8;
   bits |= 0x8;
}

becomes (let R0 = n, R1 = bits)

CMP R0, $0xff
MOVHI R0, R0, LSR $8
ORRHI R1, R1, $0x8

More Related Contents:

  1. How to check if a number is a power of 2
  2. All Possible Combinations of a list of Values
  3. Algorithm for simplifying decimal to fractions
  4. Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?
  5. Algorithm to find which numbers from a list of size n sum to another number
  6. How can I generate truly (not pseudo) random numbers with C#?
  7. What is the fastest way to compute sin and cos together?
  8. Algorithm for Calculating Binomial Coefficient
  9. Best algorithm for evaluating a mathematical expression?
  10. Select N random elements from a List in C#
  11. How to find all partitions of a set
  12. Smoothly connecting circle centers
  13. Double precision problems on .NET
  14. 3D relative angle sum calculation
  15. How to tell whether a point is to the right or left side of a line
  16. Finding all combinations of well-formed brackets
  17. Best hashing algorithm in terms of hash collisions and performance for strings
  18. Rotate a point by another point in 2D
  19. Reversible shuffle algorithm using a key
  20. Gaussian elimination without result for acceleration
  21. Special simple random number generator
  22. How do you do *integer* exponentiation in C#?
  23. Find if point lies on line segment
  24. Inverting a 4×4 matrix
  25. How does this bitwise operation check for a power of 2?
  26. Checking string has balanced parentheses
  27. All cases covered Bresenham’s line-algorithm [closed]
  28. Implementing Luhn algorithm using C#
  29. A possible algorithm for determining whether two strings are anagrams of one another? [closed]
  30. Why doesn’t C# use arithmetic overflow checking by default? [duplicate]

Leave a Comment