Find bit position without using Log()

Question

I have an integer input that is power of 2 (1, 2, 4, 8 etc). I want the function to return bit position without using log(). For example, for inputs above will return {0, 1, 2, 3} respectively This for C#. Plus if this can be done in SQL.

Thanks!

Answer 1

I don't have VS on my Mac to test this out, but did you want something like this?

public static int Foo(int n)
{
    if (n <= 0)
    {
        return -1; // A weird value is better than an infinite loop.
    }
    int i = 0;
    while (n % 2 == 0)
    {
        n /= 2;
        i++;
    }

    return i;
}

Answer 2

The fastest code I found to do this is from the Bit Twiddling Hacks site. Specifically, the lookup based on the DeBruijn sequence. See http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn

I tested a naive method, a switch-based method, and two of the Bit Twiddling Hacks methods: the DeBruijn sequence, and the other that says, "if you know your value is a power of two."

I ran all of these against an array of 32 million powers of two. That is, integers of the form 2^N, where N is in the range 0..30. A value of 2^31 is a negative number, which causes the naive method to go into an infinite loop.

I compiled the code with Visual Studio 2010 in release mode and ran it without the debugger (i.e. Ctrl+F5). On my system, the averages over several dozen runs are:

• Naive method: 950 ms
• Switch method: 660 ms
• Bithack method 1: 1,154 ms
• DeBruijn: 105 ms

It's clear that the DeBruijn sequence method is much faster than any of the others. The other Bithack method is inferior here because the conversion from C to C# results in some inefficiencies. For example, the C statement int r = (v & b[0]) != 0; ends up requiring an if or a ternary operator (i.e. ?:) in C#.

Here's the code.

class Program
{
    const int Million = 1000 * 1000;
    static readonly int NumValues = 32 * Million;

    static void Main(string[] args)
    {
        // Construct a table of integers.
        // These are random powers of two.
        // That is 2^N, where N is in the range 0..31.
        Console.WriteLine("Constructing table");
        int[] values = new int[NumValues];
        Random rnd = new Random();
        for (int i = 0; i < NumValues; ++i)
        {
            int pow = rnd.Next(31);
            values[i] = 1 << pow;
        }

        // Run each one once to make sure it's JITted
        GetLog2_Bithack(values[0]);
        GetLog2_DeBruijn(values[0]);
        GetLog2_Switch(values[0]);
        GetLog2_Naive(values[0]);

        Stopwatch sw = new Stopwatch();
        Console.Write("GetLog2_Naive ... ");
        sw.Restart();
        for (int i = 0; i < NumValues; ++i)
        {
            GetLog2_Naive(values[i]);
        }
        sw.Stop();
        Console.WriteLine("{0:N0} ms", sw.ElapsedMilliseconds);

        Console.Write("GetLog2_Switch ... ");
        sw.Restart();
        for (int i = 0; i < NumValues; ++i)
        {
            GetLog2_Switch(values[i]);
        }
        sw.Stop();
        Console.WriteLine("{0:N0} ms", sw.ElapsedMilliseconds);

        Console.Write("GetLog2_Bithack ... ");
        sw.Restart();
        for (int i = 0; i < NumValues; ++i)
        {
            GetLog2_Bithack(values[i]);
        }
        Console.WriteLine("{0:N0} ms", sw.ElapsedMilliseconds);

        Console.Write("GetLog2_DeBruijn ... ");
        sw.Restart();
        for (int i = 0; i < NumValues; ++i)
        {
            GetLog2_DeBruijn(values[i]);
        }
        sw.Stop();
        Console.WriteLine("{0:N0} ms", sw.ElapsedMilliseconds);


        Console.ReadLine();
    }

    static int GetLog2_Naive(int v)
    {
        int r = 0;
        while ((v = v >> 1) != 0)
        {
            ++r;
        }
        return r;
    }

    static readonly int[] MultiplyDeBruijnBitPosition2 = new int[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
    };

    static int GetLog2_DeBruijn(int v)
    {
        return MultiplyDeBruijnBitPosition2[(uint)(v * 0x077CB531U) >> 27];
    }

    static readonly uint[] b = new uint[] { 0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 0xFFFF0000};

    static int GetLog2_Bithack(int v)
    {
        int r = (v & b[0]) == 0 ? 0 : 1;
        int x = 1 << 4;
        for (int i = 4; i > 0; i--) // unroll for speed...
        {
            if ((v & b[i]) != 0)
                r |= x;
            x >>= 1;
        }
        return r;
    }

    static int GetLog2_Switch(int v)
    {
        switch (v)
        {
            case 0x00000001: return 0;
            case 0x00000002: return 1;
            case 0x00000004: return 2;
            case 0x00000008: return 3;
            case 0x00000010: return 4;
            case 0x00000020: return 5;
            case 0x00000040: return 6;
            case 0x00000080: return 7;
            case 0x00000100: return 8;
            case 0x00000200: return 9;
            case 0x00000400: return 10;
            case 0x00000800: return 11;
            case 0x00001000: return 12;
            case 0x00002000: return 13;
            case 0x00004000: return 14;
            case 0x00008000: return 15;
            case 0x00010000: return 16;
            case 0x00020000: return 17;
            case 0x00040000: return 18;
            case 0x00080000: return 19;
            case 0x00100000: return 20;
            case 0x00200000: return 21;
            case 0x00400000: return 22;
            case 0x00800000: return 23;
            case 0x01000000: return 24;
            case 0x02000000: return 25;
            case 0x04000000: return 26;
            case 0x08000000: return 27;
            case 0x10000000: return 28;
            case 0x20000000: return 29;
            case 0x40000000: return 30;
            case int.MinValue: return 31;
            default:
                return -1;
        }
    }
}

If I optimize the Bithack code by unrolling the loop and using constants instead of array lookups, its time is the same as the time for the switch statement method.

static int GetLog2_Bithack(int v)
{
    int r = ((v & 0xAAAAAAAA) != 0) ? 1 : 0;
    if ((v & 0xFFFF0000) != 0) r |= (1 << 4);
    if ((v & 0xFF00FF00) != 0) r |= (1 << 3);
    if ((v & 0xF0F0F0F0) != 0) r |= (1 << 2);
    if ((v & 0xCCCCCCCC) != 0) r |= (1 << 1);
    return r;
}

Answer 3

0] if number is zero or negative, return/throw error

1] In your language, find the construct that converts a number to base 2.

2] convert the base-2 value to string

3] return the length of the string minus 1.

Answer 4

Verbose code, but probably the fastest:

if (x < 1)
    throw SomeException();
if (x < 2)
    return 0;
if (x < 4)
    return 1;
if (x < 8)
    return 2;
//.... etc.

This involves no division, nor conversion to-from double. It requires only comparisons, which are very speedy. See Code Complete, 2nd edition, page 633, for a discussion.

If you know that the input will always be a power of two, you might get better performance from a switch block:

switch (input)
{
    case 1:
        return 0;
    case 2:
        return 1;
    case 4:
        return 2;
    case 8:
        return 3;
    //...
    default:
        throw SomeException();
}

I tested the performance on 10 million random ints, and on 10 million randomly-selected powers of two. The results:

• Bithacks 1: 1360 milliseconds
• Bithacks 2: 1103 milliseconds
• If: 1320 milliseconds
• Bithacks 1 (powers of 2): 1335 milliseconds
• Bithacks 2 (powers of 2): 1060 milliseconds
• Bithacks 3 (powers of 2): 1286 milliseconds
• If (powers of 2): 1026 milliseconds
• Switch (powers of 2): 896 milliseconds

I increased the number of iterations by ten times, and got these results:

• Bithacks 1: 13347 milliseconds
• Bithacks 2: 10370 milliseconds
• If: 12918 milliseconds
• Bithacks 1 (powers of 2): 12528 milliseconds
• Bithacks 2 (powers of 2): 10150 milliseconds
• Bithacks 3 (powers of 2): 12384 milliseconds
• If (powers of 2): 9969 milliseconds
• Switch (powers of 2): 8937 milliseconds

Now I didn't do any profiling to see if I did something stupid in translating the bit hacks to C# code, nor to see how much of the execution time is spent in the function that computes the log. So this is just a back-of-the-envelope kind of calculation, but it does suggest that the if approach is about the same as the bit hacks algorithms, and switch is a bit faster. Additionally, the if and switch approaches are far easier to understand and maintain.

Answer 5

This is a CPU friendly way to do it:

int bitpos=-1;
while(num>0) {
    num = num>>1;
    bitpos++;
}
return bitpos;

For SQL, use CASE. You can do binary search using nested IF....ELSE if performance is a concern. But with just 32 possible values, the overheads of implementing it could be much more than something simple sequential search.

Answer 6

find bit position in a power-of-two byte (uint8 Flag with only one bit set) coded in C (don't know about C#)

This returns the bit position 1..8 - you may need to decrement the result for indexing 0..7.

int pos(int a){
    int p = (a & 3) | ((a >> 1) & 6) | ((a >> 2) & 5) | ((a >> 3) & 4) | ((a >> 4) & 15) | ((a >> 5) & 2) | ((a >> 6) & 1);
    return p;
}

For info on the "evolution" of the code snippet see my blogpost here http://blog.edutoolbox.de/?p=263

EDIT:

deBruijn style is about 100x faster ...