CODEWITHSUNDEEP
c#biginteger
Paul Chernoch
Paul Chernoch

Reputation: 5553

Find most significant bit of a BigInteger

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.

The naive way is:

BigInteger n = 234762348763498247634; 
int count = 0; 
while (n > 0) {
    n >>= 1;
    count++;
}

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?

One intended use for this function is to help optimize inverse gray code calculations.

Update. I coded two approaches and ran a benchmark.

Here is the code for using Log:

public static int MostSignificantBitUsingLog(BigInteger i)
{
    int bit;
    if (i == 0)
        bit = -1;
    else
        bit = (int)BigInteger.Log(i, 2.0);

    return bit;
}

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.

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;
}

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.)

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;
}

Upvotes: 1

Views: 3471

Answers (5)

SunsetQuest
SunsetQuest

Reputation: 8837

In .Net 5 this is now built-in...

int log2 = myBigInt.GetBitLength()

Upvotes: 1

SunsetQuest
SunsetQuest

Reputation: 8837

8 years late, to find the MSB top bit (aka Log2) I came up with this quick method...

static int GetTopBit(BigInteger value)
{
    if (value < 0)
        BigInteger.Negate(value);
    int lowerBytes = value.GetByteCount(true) - 1;
    int t = value.ToByteArray(true)[lowerBytes];
    int top = t > 127 ? 8 : t > 63 ? 7 : t > 31 ? 6 : t > 15 ? 5 : t > 7 ? 4 : t > 3 ? 3 : t > 1 ? 2 : 1;
    int topbit = (top + lowerBytes * 8);
    return topbit;
}

Upvotes: 0

Daniel
Daniel

Reputation: 26

If you can use Java rather than C#, there is a library for arbitrary precision Hilbert curve indexing that you can find at http://uzaygezen.googlecode.com. For the implementation of the gray code inverse, you may want to have a closer look at LongArrayBitVector.grayCodeInverse or perhaps BitSetBackedVector.grayCodeInverse in the mentioned project.

Upvotes: 0

Henk Holterman
Henk Holterman

Reputation: 273464

You can treat it like a binary-search problem.

You have an upper limit of 4000 (add some room maybe)

int m = (lo + hi) / 2;
BigInteger x = BigInteger(1) << m;

if (x > n) ...
else  ...

Upvotes: 2

usr
usr

Reputation: 171206

You can calculate the log2 which represent the number of bits needed:

var numBits = (int)Math.Ceil(bigInt.Log(2));

Upvotes: 5

Related Questions