CODEWITHSUNDEEP
algorithmbinarylogarithm
alpha42
alpha42

Reputation: 53

Computing the floor log of a binary number

If there is a number in binary, in a n bit system, then the floor log of the number is defined as the index of the MSB of the number. Now, if I have a number in binary, By scanning all bits one by one, I can determine the index of the MSB, but it will take me order n time. Is there some faster way I can do it?

Upvotes: 2

Views: 1240

Answers (2)

mbsullivan
mbsullivan

Reputation: 29

There are a number of general tricks that utilize small lookup tables, as @hatchet says.

There is a notable alternative, however. If you want the fastest implementation and are using a low-level language, then this instruction is also built into almost all ISAs and has support from almost all compilers. See https://en.wikipedia.org/wiki/Find_first_set and use compiler intrinsics or inline assembly as appropriate.

Upvotes: 1

hatchet - done with SOverflow
hatchet - done with SOverflow

Reputation: 16257

Using c# as an example, for a byte, you can pre-compute a table and then just do a lookup

internal static readonly byte[] msbPos256 = new byte[256];
static ByteExtensions() {
    msbPos256[0] = 8; // special value for when there are no set bits
    msbPos256[1] = 0;
    for (int i = 2; i < 256; i++) msbPos256[i] = (byte)(1 + msbPos256[i / 2]);
}

/// <summary>
/// Returns the integer logarithm base 2 (Floor(Log2(number))) of the specified number.
/// </summary>
/// <remarks>Example: Log2(10) returns 3.</remarks>
/// <param name="number">The number whose base 2 log is desired.</param>
/// <returns>The base 2 log of the number greater than 0, or 0 when the number
/// equals 0.</returns>
public static byte Log2(this byte value) {
    return msbPos256[value | 1];
}

for an unsigned 32 bit int, the following will work

private static byte[] DeBruijnLSBsSet = new byte[] {
    0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
    8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
public static uint Log2(this uint value) {
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    return DeBruijnLSBsSet[unchecked((value | value >> 16) * 0x07c4acddu) >> 27];
}

This website is the go-to place for bit twiddling tricks

http://graphics.stanford.edu/~seander/bithacks.html

It has these, and a number of other techniques for achieving what you are asking for in your question.

Upvotes: 2

Related Questions