0

Say I'm given n=32. I want to know what log_2(n) is. In this 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.

Olhovsky
  • 5,466
  • 3
  • 36
  • 47
  • Is n constrained? Is it (for example) an int or a long? (so k <= 31 or <= 63) – xanatos Mar 17 '11 at 14:43
  • possible duplicate of [How to do an integer log2() in C++?](http://stackoverflow.com/questions/994593/how-to-do-an-integer-log2-in-c) – paxdiablo Mar 17 '11 at 15:13
  • I am very confused about why this question recieved a bunch of upvotes, followed by a bunch of downvotes, and now sits at -1. What was wrong with this question? It is especially confusing in light of the fact that it lead to a wonderful answer by Eric Lippert below. – Olhovsky Jan 05 '12 at 06:29

2 Answers2

15

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.

Eric Lippert
  • 647,829
  • 179
  • 1,238
  • 2,067
  • 1
    Just out of curiosity, is there a reason for the cast to `uint`? You're already assuming that `x` is an exact power of 2 between 1 and 2**31. – LukeH Mar 17 '11 at 16:00
  • @LukeH: I'll answer your question with a question: What is (1<<31)%37 equal to in C#? Now is it clear why the cast to uint? – Eric Lippert Mar 17 '11 at 16:20
  • @Eric: Yes, but your method's `x` parameter is an `int`. Why not type the parameter as a `uint` in the first place, rather than relying on the cast to avoid exceptions? – LukeH Mar 17 '11 at 17:18
  • 1
    @LukeH: Unless told otherwise I assume that all methods are desired to take CLS-compliant types. – Eric Lippert Mar 17 '11 at 17:58
  • 3
    @Eric: Fair enough, although it feels a bit weird to purport to return the log of a negative. What you're really returning in that situation is `lg(2147483648)` not `lg(-2147483648)` which, arguably, should generate an error. (Notwithstanding that both numbers are the same from a bit-twiddling perspective.) – LukeH Mar 17 '11 at 18:11
  • @LukeH: You make an excellent point. Really the function should be named "PositionOfHighestSingleBit" or something like that; this isn't a log at all if it takes negative arguments. – Eric Lippert Mar 17 '11 at 18:19
  • 1
    @Eric: In your hypothesis, do you mean to say each power of two has a different remainder when divided by P? This would be untrue, a simple counter example is N = 6, P = 7: 2^2 mod 7 ≡ 2^5 mod 7 = 4. – LBushkin Mar 17 '11 at 23:45
  • The one thing I don't like about the solution is that it doesn't make sure x is actually a power of 2 - and if it isn't, a nonsensical result is pretty much promised. Maybe it should have a `Debug.Assert(Math.Pow(result, 2) == x)`? – configurator Mar 22 '11 at 17:04
  • @configurator: Indeed. This was intended merely as a sketch of the core idea of the solution and not an actual implementation of a public method that I'd be happy with shipping to customers as part of the base class library. – Eric Lippert Mar 22 '11 at 17:12
1

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;
Roly
  • 1,516
  • 1
  • 15
  • 26
  • 1
    Wouldn't the length of the string be sufficient or does Convert.ToString include leading zeros? (EDIT -- string length - 1) – Austin Salonen Mar 17 '11 at 14:57
  • I thought about it after I responded, and I think I just interpreted "fastest way" as most obvious and easiest to implement with least amount of code. Otherwise the question would've been "what's the most efficient way..." – Roly Mar 17 '11 at 15:17