StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POFind most significant bit of a BigInteger
text
Body
copied!<p>I have read many fine algorithms for identifying the most significant bit for 32- and 64-bit integers (including other posts here on SO). But I am using BigIntegers, and will be dealing with numbers up to 4000 bits long. (The BigInteger will hold the Hilbert index into the Hilbert space-filling curve that meanders through a 1000-dimension hypercube at a fractal depth of 4.) But the bulk of the cases will involve numbers that could fit inside a 64 bit integer, so I want a solution that is optimal for the common cases but can handle the extreme cases.</p> <p>The naive way is:</p> <pre><code>BigInteger n = 234762348763498247634; int count = 0; while (n > 0) { n >>= 1; count++; } </code></pre> <p>I was thinking of converting common cases to Longs and using a 64-bit algorithm on those, otherwise using a different algorithm for the really big numbers. But I am not sure how expensive the conversion to a Long is, and whether that will swamp the efficiencies of doing the remainder of the computation on a 64-bit quantity. Any thoughts? </p> <p>One intended use for this function is to help optimize inverse gray code calculations.</p> <p>Update. I coded two approaches and ran a benchmark.</p> <ul> <li>If the number was under Ulong.MaxValue, then converting to a Ulong and doing the binary search approach was twice as fast as using BigInteger.Log.</li> <li><p>If the number was very large (I went as high as 10000 bits), then Log was 3.5 times faster.</p> <p>96 msec elapsed for one million calls to MostSignificantBitUsingLog (convertable to Long).</p> <p>42 msec elapsed for one million calls to MostSignificantBitUsingBinarySearch (convertable to Long).</p> <p>74 msec elapsed for ten thousand calls to MostSignificantBitUsingLog (too big to convert).</p> <p>267 msec elapsed for ten thousand calls to MostSignificantBitUsingBinarySearch (too big to convert).</p></li> </ul> <p>Here is the code for using Log:</p> <pre><code>public static int MostSignificantBitUsingLog(BigInteger i) { int bit; if (i == 0) bit = -1; else bit = (int)BigInteger.Log(i, 2.0); return bit; } </code></pre> <p>Here is my approach to binary search. It could be improved to extend the binary division up into the BigInteger range. I will try that next.</p> <pre><code>public static int MostSignificantBitUsingBinarySearch(BigInteger i) { int bit; if (i.IsZero) bit = -1; else if (i < ulong.MaxValue) { ulong y = (ulong)i; ulong s; bit = 0; s = y >> 32; if (s != 0) { bit = 32; y = s; } s = y >> 16; if (s != 0) { bit += 16; y = s; } s = y >> 8; if (s != 0) { bit += 8; y = s; } s = y >> 4; if (s != 0) { bit += 4; y = s; } s = y >> 2; if (s != 0) { bit += 2; y = s; } s = y >> 1; if (s != 0) bit++; } else return 64 + MostSignificantBitUsingBinarySearch(i >> 64); return bit; } </code></pre> <p>Update 2: I changed my binary search algorithm to work against BigIntegers up to one million binary digits and not call itself recursively in 64 bit chunks. Much better. Now it takes 18 msec to run my test, and is four times faster than calling Log! (In the code below, MSB is my ulong function that does the same sort of thing, with the loop unrolled.)</p> <pre><code>public static int MostSignificantBitUsingBinarySearch(BigInteger i) { int bit; if (i.IsZero) bit = -1; else if (i < ulong.MaxValue) bit = MSB((ulong)i); else { bit = 0; int shift = 1 << 20; // Accommodate up to One million bits. BigInteger remainder; while (shift > 0) { remainder = i >> shift; if (remainder != 0) { bit += shift; i = remainder; } shift >>= 1; } } return bit; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload