Bit hacks to compute floor(log2(int))

I wrote a program in the last day to determine the fastest method of seven implementations that I found over the Web that solves the operation “floor(log2(int))”. This operation takes an integer and determines the position of the topmost bit that is one. So, for example floor(log2(0x2)) would be 1, floor(log2(0x52)) would be 6. This operation is important in finding the nearest common ancestor of a tree (more on this in a book that I am writing).

One of the seven methods I found involves a call to x86 code that executes a BSR instruction. The code works, but alas, it is not the fastest. Unfortunately, there does not seem to be a way to easily inline assembly or IL code into C# code.

The output below are the times in milliseconds for the seven different methods. The straight-forward approach (“method 1”) yields the slowest; the fastest (“method 3”) was 22% of the time of the slowest.



=====================
Output:

Method 1
1899.7615
Method 2
459.0597
Method 3 - variation on method 2
428.3438
Method 4
1406.9156
Method 5
785.6121
Method 6
631.4484
Method 7
1038.5484

=====================

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Runtime.InteropServices; // DllImport

namespace FloorLog2
{
    public class Asm
    {
        [DllImport("Asm.Dll")]
        public static extern int method7(int x);
    }

    class Program
    {

        // From http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
        int method1(uint v)
        {
            uint x = 0;
            while ((v = (v >> 1)) != 0)
            {
                x++;
            }
            return (int)x;
        }

        int[] LogTable256 = new int[256];
        void prep()
        {
            LogTable256[0] = LogTable256[1] = 0;
            for (int i = 2; i < 256; i++)
            {
                LogTable256[i] = 1 + LogTable256[i / 2];
            }
            LogTable256[0] = -1; // if you want log(0) to return -1
        }

        int method2(uint v)
        {
            int r;
            uint t, tt;

            if ((tt = v >> 16) != 0)
            {
                r = ((t = tt >> 8 ) != 0) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
            }
            else
            {
                r = ((t = v >> 8 ) != 0) ? 8 + LogTable256[t] : LogTable256[v];
            }
            return r;
        }

        int method3(uint v)
        {
            int r;     // r will be lg(v)
            uint tt; // temporaries

            if ((tt = v >> 24) != 0)
            {
                r = (24 + LogTable256[tt]);
            }
            else if ((tt = v >> 16) != 0)
            {
                r = (16 + LogTable256[tt]);
            }
            else if ((tt = v >> 8 ) != 0)
            {
                r = (8 + LogTable256[tt]);
            }
            else
            {
                r = LogTable256[v];
            }
            return r;
        }

        int method4(uint v)
        {
            uint[] b = new uint[] { 0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000 };
            int[] S = new int[] { 1, 2, 4, 8, 16 };
            int i;

            uint r = 0;
            for (i = 4; i >= 0; i--)
            {
                if ((v & b[i]) != 0)
                {
                    v = v >> S[i];
                    r |= (uint)S[i];
                }
            }
            return (int)r;
        }

        // From http://www.aggregate.org/MAGIC/
        int method5(uint v)
        {
            v |= (v >> 1);
            v |= (v >> 2);
            v |= (v >> 4);
            v |= (v >> 8);
            v |= (v >> 16);
            return (int)ones32(v) - 1;
        }

        uint ones32(uint x)
        {
            x -= ((x >> 1) & 0x55555555);
            x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
            x = (((x >> 4) + x) & 0x0f0f0f0f);
            x += (x >> 8);
            x += (x >> 16);
            return(x & 0x0000003f);
        }

        // From http://en.wikipedia.org/wiki/Binary_logarithm
        int method6(uint v)
        {
            int pos = 0;
            if (v >= 1<<16) { v >>= 16; pos += 16; }
            if (v >= 1<< 8) { v >>=  8; pos +=  8; }
            if (v >= 1<< 4) { v >>=  4; pos +=  4; }
            if (v >= 1<< 2) { v >>=  2; pos +=  2; }
            if (v >= 1<< 1) {           pos +=  1; }
            return ((v == 0) ? (-1) : pos);
        }

        static void Main(string[] args)
        {
            Program ops = new Program();
            ops.prep();

            // Sanity check
            uint n = 1;
            for (int k = 0; k < 32; ++k)
            {
                int r1 = ops.method1(n);
                int r2 = ops.method2(n);
                int r3 = ops.method3(n);
                int r4 = ops.method4(n);
                int r5 = ops.method5(n);
                int r6 = ops.method6(n);
                int r7 = Asm.method7((int)n);
                if (r1 != r2 || r1 != r3 || r1 != r4 || r1 != r5 || r1 != r6 || r1 != r7)
                    throw new Exception("Incorrect value");
                n = n << 1;
            }
            n = 5;
            for (int k = 0; k < 29; ++k)
            {
                int r1 = ops.method1(n);
                int r2 = ops.method2(n);
                int r3 = ops.method3(n);
                int r4 = ops.method4(n);
                int r5 = ops.method5(n);
                int r6 = ops.method6(n);
                int r7 = Asm.method7((int)n);
                if (r1 != r2 || r1 != r3 || r1 != r4 || r1 != r5 || r1 != r6 || r1 != r7)
                    throw new Exception("Incorrect value");
                n = n << 1;
            }
            n = 0xffffffff;
            {
                int r1 = ops.method1(n);
                int r2 = ops.method2(n);
                int r3 = ops.method3(n);
                int r4 = ops.method4(n);
                int r5 = ops.method5(n);
                int r6 = ops.method6(n);
                int r7 = Asm.method7((int)n);
                if (r1 != r2 || r1 != r3 || r1 != r4 || r1 != r5 || r1 != r6 || r1 != r7)
                    throw new Exception("Incorrect value");
                n = n << 1;
            }

            // Time some bit twittle operations
            // Most significant bit of a 32-bit integer.
            Stopwatch sw = new Stopwatch();

            System.Console.WriteLine("Method 1");
            {
                Random rand = new Random();
                sw.Reset();
                sw.Start();
                for (int i = 0; i < 10000000; ++i)
                {
                    uint v = (uint)rand.Next();
                    ops.method1(v);
                }
                sw.Stop();
                System.Console.WriteLine(sw.Elapsed.TotalMilliseconds);
            }

            System.Console.WriteLine("Method 2");
            {
                Random rand = new Random();
                sw.Reset();
                sw.Start();
                for (int i = 0; i < 10000000; ++i)
                {
                    uint v = (uint)rand.Next();
                    ops.method2(v);
                }
                sw.Stop();
                System.Console.WriteLine(sw.Elapsed.TotalMilliseconds);
            }

            System.Console.WriteLine("Method 3 - variation on method 2");
            {
                Random rand = new Random();
                sw.Reset();
                sw.Start();
                for (int i = 0; i < 10000000; ++i)
                {
                    uint v = (uint)rand.Next();
                    ops.method3(v);
                }
                sw.Stop();
                System.Console.WriteLine(sw.Elapsed.TotalMilliseconds);
            }

            System.Console.WriteLine("Method 4");
            {
                Random rand = new Random();
                sw.Reset();
                sw.Start();
                for (int i = 0; i < 10000000; ++i)
                {
                    uint v = (uint)rand.Next();
                    ops.method4(v);
                }
                sw.Stop();
                System.Console.WriteLine(sw.Elapsed.TotalMilliseconds);
            }

            System.Console.WriteLine("Method 5");
            {
                Random rand = new Random();
                sw.Reset();
                sw.Start();
                for (int i = 0; i < 10000000; ++i)
                {
                    uint v = (uint)rand.Next();
                    ops.method5(v);
                }
                sw.Stop();
                System.Console.WriteLine(sw.Elapsed.TotalMilliseconds);
            }

            System.Console.WriteLine("Method 6");
            {
                Random rand = new Random();
                sw.Reset();
                sw.Start();
                for (int i = 0; i < 10000000; ++i)
                {
                    uint v = (uint)rand.Next();
                    ops.method6(v);
                }
                sw.Stop();
                System.Console.WriteLine(sw.Elapsed.TotalMilliseconds);
            }

            System.Console.WriteLine("Method 7");
            {
                Random rand = new Random();
                sw.Reset();
                sw.Start();
                for (int i = 0; i < 10000000; ++i)
                {
                    uint v = (uint)rand.Next();
                    Asm.method7((int)v);
                }
                sw.Stop();
                System.Console.WriteLine(sw.Elapsed.TotalMilliseconds);
            }
        }
    }
}

===================
asm.cpp:

extern "C" __declspec(dllexport) int method7(unsigned int v)
{
	int msb;
	__asm {
		mov ebx,msb
		bsr ebx,v
		mov msb,ebx
	}
	return msb;
}

Posted in Tip

0 thoughts on “Bit hacks to compute floor(log2(int))

Comments are closed.