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).
\n<\/p>\n
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.<\/p>\n
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.<\/p>\n
\r\n\r\n=====================\r\nOutput:\r\n\r\nMethod 1\r\n1899.7615\r\nMethod 2\r\n459.0597\r\nMethod 3 - variation on method 2\r\n428.3438\r\nMethod 4\r\n1406.9156\r\nMethod 5\r\n785.6121\r\nMethod 6\r\n631.4484\r\nMethod 7\r\n1038.5484\r\n\r\n=====================\r\n\r\nusing System;\r\nusing System.Collections.Generic;\r\nusing System.Linq;\r\nusing System.Text;\r\nusing System.Diagnostics;\r\nusing System.Runtime.InteropServices; \/\/ DllImport\r\n\r\nnamespace FloorLog2\r\n{\r\n public class Asm\r\n {\r\n [DllImport(\"Asm.Dll\")]\r\n public static extern int method7(int x);\r\n }\r\n\r\n class Program\r\n {\r\n\r\n \/\/ From http:\/\/graphics.stanford.edu\/~seander\/bithacks.html#IntegerLogObvious\r\n int method1(uint v)\r\n {\r\n uint x = 0;\r\n while ((v = (v >> 1)) != 0)\r\n {\r\n x++;\r\n }\r\n return (int)x;\r\n }\r\n\r\n int[] LogTable256 = new int[256];\r\n void prep()\r\n {\r\n LogTable256[0] = LogTable256[1] = 0;\r\n for (int i = 2; i < 256; i++)\r\n {\r\n LogTable256[i] = 1 + LogTable256[i \/ 2];\r\n }\r\n LogTable256[0] = -1; \/\/ if you want log(0) to return -1\r\n }\r\n\r\n int method2(uint v)\r\n {\r\n int r;\r\n uint t, tt;\r\n\r\n if ((tt = v >> 16) != 0)\r\n {\r\n r = ((t = tt >> 8 ) != 0) ? 24 + LogTable256[t] : 16 + LogTable256[tt];\r\n }\r\n else\r\n {\r\n r = ((t = v >> 8 ) != 0) ? 8 + LogTable256[t] : LogTable256[v];\r\n }\r\n return r;\r\n }\r\n\r\n int method3(uint v)\r\n {\r\n int r; \/\/ r will be lg(v)\r\n uint tt; \/\/ temporaries\r\n\r\n if ((tt = v >> 24) != 0)\r\n {\r\n r = (24 + LogTable256[tt]);\r\n }\r\n else if ((tt = v >> 16) != 0)\r\n {\r\n r = (16 + LogTable256[tt]);\r\n }\r\n else if ((tt = v >> 8 ) != 0)\r\n {\r\n r = (8 + LogTable256[tt]);\r\n }\r\n else\r\n {\r\n r = LogTable256[v];\r\n }\r\n return r;\r\n }\r\n\r\n int method4(uint v)\r\n {\r\n uint[] b = new uint[] { 0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000 };\r\n int[] S = new int[] { 1, 2, 4, 8, 16 };\r\n int i;\r\n\r\n uint r = 0;\r\n for (i = 4; i >= 0; i--)\r\n {\r\n if ((v & b[i]) != 0)\r\n {\r\n v = v >> S[i];\r\n r |= (uint)S[i];\r\n }\r\n }\r\n return (int)r;\r\n }\r\n\r\n \/\/ From http:\/\/www.aggregate.org\/MAGIC\/\r\n int method5(uint v)\r\n {\r\n v |= (v >> 1);\r\n v |= (v >> 2);\r\n v |= (v >> 4);\r\n v |= (v >> 8);\r\n v |= (v >> 16);\r\n return (int)ones32(v) - 1;\r\n }\r\n\r\n uint ones32(uint x)\r\n {\r\n x -= ((x >> 1) & 0x55555555);\r\n x = (((x >> 2) & 0x33333333) + (x & 0x33333333));\r\n x = (((x >> 4) + x) & 0x0f0f0f0f);\r\n x += (x >> 8);\r\n x += (x >> 16);\r\n return(x & 0x0000003f);\r\n }\r\n\r\n \/\/ From http:\/\/en.wikipedia.org\/wiki\/Binary_logarithm\r\n int method6(uint v)\r\n {\r\n int pos = 0;\r\n if (v >= 1<<16) { v >>= 16; pos += 16; }\r\n if (v >= 1<< 8) { v >>= 8; pos += 8; }\r\n if (v >= 1<< 4) { v >>= 4; pos += 4; }\r\n if (v >= 1<< 2) { v >>= 2; pos += 2; }\r\n if (v >= 1<< 1) { pos += 1; }\r\n return ((v == 0) ? (-1) : pos);\r\n }\r\n\r\n static void Main(string[] args)\r\n {\r\n Program ops = new Program();\r\n ops.prep();\r\n\r\n \/\/ Sanity check\r\n uint n = 1;\r\n for (int k = 0; k < 32; ++k)\r\n {\r\n int r1 = ops.method1(n);\r\n int r2 = ops.method2(n);\r\n int r3 = ops.method3(n);\r\n int r4 = ops.method4(n);\r\n int r5 = ops.method5(n);\r\n int r6 = ops.method6(n);\r\n int r7 = Asm.method7((int)n);\r\n if (r1 != r2 || r1 != r3 || r1 != r4 || r1 != r5 || r1 != r6 || r1 != r7)\r\n throw new Exception(\"Incorrect value\");\r\n n = n << 1;\r\n }\r\n n = 5;\r\n for (int k = 0; k < 29; ++k)\r\n {\r\n int r1 = ops.method1(n);\r\n int r2 = ops.method2(n);\r\n int r3 = ops.method3(n);\r\n int r4 = ops.method4(n);\r\n int r5 = ops.method5(n);\r\n int r6 = ops.method6(n);\r\n int r7 = Asm.method7((int)n);\r\n if (r1 != r2 || r1 != r3 || r1 != r4 || r1 != r5 || r1 != r6 || r1 != r7)\r\n throw new Exception(\"Incorrect value\");\r\n n = n << 1;\r\n }\r\n n = 0xffffffff;\r\n {\r\n int r1 = ops.method1(n);\r\n int r2 = ops.method2(n);\r\n int r3 = ops.method3(n);\r\n int r4 = ops.method4(n);\r\n int r5 = ops.method5(n);\r\n int r6 = ops.method6(n);\r\n int r7 = Asm.method7((int)n);\r\n if (r1 != r2 || r1 != r3 || r1 != r4 || r1 != r5 || r1 != r6 || r1 != r7)\r\n throw new Exception(\"Incorrect value\");\r\n n = n << 1;\r\n }\r\n\r\n \/\/ Time some bit twittle operations\r\n \/\/ Most significant bit of a 32-bit integer.\r\n Stopwatch sw = new Stopwatch();\r\n\r\n System.Console.WriteLine(\"Method 1\");\r\n {\r\n Random rand = new Random();\r\n sw.Reset();\r\n sw.Start();\r\n for (int i = 0; i < 10000000; ++i)\r\n {\r\n uint v = (uint)rand.Next();\r\n ops.method1(v);\r\n }\r\n sw.Stop();\r\n System.Console.WriteLine(sw.Elapsed.TotalMilliseconds);\r\n }\r\n\r\n System.Console.WriteLine(\"Method 2\");\r\n {\r\n Random rand = new Random();\r\n sw.Reset();\r\n sw.Start();\r\n for (int i = 0; i < 10000000; ++i)\r\n {\r\n uint v = (uint)rand.Next();\r\n ops.method2(v);\r\n }\r\n sw.Stop();\r\n System.Console.WriteLine(sw.Elapsed.TotalMilliseconds);\r\n }\r\n\r\n System.Console.WriteLine(\"Method 3 - variation on method 2\");\r\n {\r\n Random rand = new Random();\r\n sw.Reset();\r\n sw.Start();\r\n for (int i = 0; i < 10000000; ++i)\r\n {\r\n uint v = (uint)rand.Next();\r\n ops.method3(v);\r\n }\r\n sw.Stop();\r\n System.Console.WriteLine(sw.Elapsed.TotalMilliseconds);\r\n }\r\n\r\n System.Console.WriteLine(\"Method 4\");\r\n {\r\n Random rand = new Random();\r\n sw.Reset();\r\n sw.Start();\r\n for (int i = 0; i < 10000000; ++i)\r\n {\r\n uint v = (uint)rand.Next();\r\n ops.method4(v);\r\n }\r\n sw.Stop();\r\n System.Console.WriteLine(sw.Elapsed.TotalMilliseconds);\r\n }\r\n\r\n System.Console.WriteLine(\"Method 5\");\r\n {\r\n Random rand = new Random();\r\n sw.Reset();\r\n sw.Start();\r\n for (int i = 0; i < 10000000; ++i)\r\n {\r\n uint v = (uint)rand.Next();\r\n ops.method5(v);\r\n }\r\n sw.Stop();\r\n System.Console.WriteLine(sw.Elapsed.TotalMilliseconds);\r\n }\r\n\r\n System.Console.WriteLine(\"Method 6\");\r\n {\r\n Random rand = new Random();\r\n sw.Reset();\r\n sw.Start();\r\n for (int i = 0; i < 10000000; ++i)\r\n {\r\n uint v = (uint)rand.Next();\r\n ops.method6(v);\r\n }\r\n sw.Stop();\r\n System.Console.WriteLine(sw.Elapsed.TotalMilliseconds);\r\n }\r\n\r\n System.Console.WriteLine(\"Method 7\");\r\n {\r\n Random rand = new Random();\r\n sw.Reset();\r\n sw.Start();\r\n for (int i = 0; i < 10000000; ++i)\r\n {\r\n uint v = (uint)rand.Next();\r\n Asm.method7((int)v);\r\n }\r\n sw.Stop();\r\n System.Console.WriteLine(sw.Elapsed.TotalMilliseconds);\r\n }\r\n }\r\n }\r\n}\r\n\r\n===================\r\nasm.cpp:\r\n\r\nextern \"C\" __declspec(dllexport) int method7(unsigned int v)\r\n{\r\n\tint msb;\r\n\t__asm {\r\n\t\tmov ebx,msb\r\n\t\tbsr ebx,v\r\n\t\tmov msb,ebx\r\n\t}\r\n\treturn msb;\r\n}\r\n\r\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"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 … <\/p>\n