2

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?

alpha42
  • 55
  • 6

2 Answers2

2

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.

hatchet - done with SOverflow
  • 15,919
  • 5
  • 47
  • 57
  • hi! Is it possible to extend this code to 64 bit numbers? – Denis Apr 07 '15 at 23:14
  • @Denis - I don't have a 64 bit version, but off the top of my head, I think you could do it using the above code as follows: create a uint that is the most significant 4 bytes of your value `(uint)(value >> 32)`. If that equals 0, then return Log2 of the lower 4 bytes of your 64 bit value, else return 32 + Log2 of the upper 4 bytes of your 64 bit value. – hatchet - done with SOverflow Apr 07 '15 at 23:38
  • thank you for answer. It seems, that I find 64 version of this code: http://stackoverflow.com/a/3465395/1756750 – Denis Apr 07 '15 at 23:41
1

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.

mbsullivan
  • 29
  • 4