What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?

GCC has:

 -- Built-in Function: int __builtin_clz (unsigned int x)
     Returns the number of leading 0-bits in X, starting at the most
     significant bit position.  If X is 0, the result is undefined.

 -- Built-in Function: int __builtin_clzl (unsigned long)
     Similar to `__builtin_clz', except the argument type is `unsigned
     long'.

 -- Built-in Function: int __builtin_clzll (unsigned long long)
     Similar to `__builtin_clz', except the argument type is `unsigned
     long long'.

I'd expect them to be translated into something reasonably efficient for your current platform, whether it be one of those fancy bit-twiddling algorithms, or a single instruction.

A useful trick if your input can be zero is __builtin_clz(x | 1): unconditionally setting the low bit without modifying any others makes the output 31 for x=0, without changing the output for any other input.

To avoid needing to do that, your other option is platform-specific intrinsics like ARM GCC's __clz (no header needed), or x86's _lzcnt_u32 on CPUs that support the lzcnt instruction. (Beware that lzcnt decodes as bsr on older CPUs instead of faulting, which gives 31-lzcnt for non-zero inputs.)

There's unfortunately no way to portably take advantage of the various CLZ instructions on non-x86 platforms that do define the result for input=0 as 32 or 64 (according to the operand width). x86's lzcnt does that, too, while bsr produces a bit-index that the compiler has to flip unless you use 31-__builtin_clz(x).

(The "undefined result" is not C Undefined Behavior, just a value that isn't defined. It's actually whatever was in the destination register when the instruction ran. AMD documents this, Intel doesn't, but Intel's CPUs do implement that behaviour. But it's not whatever was previously in the C variable you're assigning to, that's not usually how things work when gcc turns C into asm. See also Why does breaking the "output dependency" of LZCNT matter?)

Since 2^N is an integer with only the Nth bit set (1 << N), finding the position (N) of the highest set bit is the integer log base 2 of that integer.

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

unsigned int v;
unsigned r = 0;

while (v >>= 1) {
    r++;
}

This "obvious" algorithm may not be transparent to everyone, but when you realize that the code shifts right by one bit repeatedly until the leftmost bit has been shifted off (note that C treats any non-zero value as true) and returns the number of shifts, it makes perfect sense. It also means that it works even when more than one bit is set — the result is always for the most significant bit.

If you scroll down on that page, there are faster, more complex variations. However, if you know you're dealing with numbers with a lot of leading zeroes, the naive approach may provide acceptable speed, since bit shifting is rather fast in C, and the simple algorithm doesn't require indexing an array.

NOTE: When using 64-bit values, be extremely cautious about using extra-clever algorithms; many of them only work correctly for 32-bit values.

Assuming you're on x86 and game for a bit of inline assembler, Intel provides a BSR instruction ("bit scan reverse"). It's fast on some x86s (microcoded on others). From the manual:

Searches the source operand for the most significant set bit (1 bit). If a most significant 1 bit is found, its bit index is stored in the destination operand. The source operand can be a register or a memory location; the destination operand is a register. The bit index is an unsigned offset from bit 0 of the source operand. If the content source operand is 0, the content of the destination operand is undefined.

(If you're on PowerPC there's a similar cntlz ("count leading zeros") instruction.)

Example code for gcc:

#include <iostream>

int main (int,char**)
{
  int n=1;
  for (;;++n) {
    int msb;
    asm("bsrl %1,%0" : "=r"(msb) : "r"(n));
    std::cout << n << " : " << msb << std::endl;
  }
  return 0;
}

See also this inline assembler tutorial, which shows (section 9.4) it being considerably faster than looping code.

This is sort of like finding a kind of integer log. There are bit-twiddling tricks, but I've made my own tool for this. The goal of course is for speed.

My realization is that the CPU has an automatic bit-detector already, used for integer to float conversion! So use that.

double ff=(double)(v|1);
return ((*(1+(uint32_t *)&ff))>>20)-1023;  // assumes x86 endianness

This version casts the value to a double, then reads off the exponent, which tells you where the bit was. The fancy shift and subtract is to extract the proper parts from the IEEE value.

It's slightly faster to use floats, but a float can only give you the first 24 bit positions because of its smaller precision.

To do this safely, without undefined behaviour in C++ or C, use memcpy instead of pointer casting for type-punning. Compilers know how to inline it efficiently.

// static_assert(sizeof(double) == 2 * sizeof(uint32_t), "double isn't 8-byte IEEE binary64");
// and also static_assert something about FLT_ENDIAN?

double ff=(double)(v|1);

uint32_t tmp;
memcpy(&tmp, ((const char*)&ff)+sizeof(uint32_t), sizeof(uint32_t));
return (tmp>>20)-1023;

Or in C99 and later, use a union {double d; uint32_t u[2];};. But note that in C++, union type punning is only supported on some compilers as an extension, not in ISO C++.

This will usually be slower than a platform-specific intrinsic for a leading-zeros counting instruction, but portable ISO C has no such function. Some CPUs also lack a leading-zero counting instruction, but some of those can efficiently convert integers to double. Type-punning an FP bit pattern back to integer can be slow, though (e.g. on PowerPC it requires a store/reload and usually causes a load-hit-store stall).

This algorithm could potentially be useful for SIMD implementations, because fewer CPUs have SIMD lzcnt. x86 only got such an instruction with AVX512CD

This should be lightning fast:

int msb(unsigned int v) {
  static const int pos[32] = {0, 1, 28, 2, 29, 14, 24, 3,
    30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19,
    16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
  v |= v >> 1;
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;
  v = (v >> 1) + 1;
  return pos[(v * 0x077CB531UL) >> 27];
}

Although I would probably only use this method if I absolutely required the best possible performance (e.g. for writing some sort of board game AI involving bitboards), the most efficient solution is to use inline ASM. See the Optimisations section of this blog post for code with an explanation.

[...], the bsrl assembly instruction computes the position of the most significant bit. Thus, we could use this asm statement:

asm ("bsrl %1, %0" 
     : "=r" (position) 
     : "r" (number));

unsigned int
msb32(register unsigned int x)
{
        x |= (x >> 1);
        x |= (x >> 2);
        x |= (x >> 4);
        x |= (x >> 8);
        x |= (x >> 16);
        return(x & ~(x >> 1));
}

1 register, 13 instructions. Believe it or not, this is usually faster than the BSR instruction mentioned above, which operates in linear time. This is logarithmic time.

From http://aggregate.org/MAGIC/#Most%20Significant%201%20Bit

What about

int highest_bit(unsigned int a) {
    int count;
    std::frexp(a, &count);
    return count - 1;
}

?

Think bitwise operators.

I missunderstood the question the first time. You should produce an int with the leftmost bit set (the others zero). Assuming cmp is set to that value:

position = sizeof(int)*8
while(!(n & cmp)){ 
   n <<=1;
   position--;
}

Another poster provided a lookup-table using a byte-wide lookup. In case you want to eke out a bit more performance (at the cost of 32K of memory instead of just 256 lookup entries) here is a solution using a 15-bit lookup table, in C# 7 for .NET.

The interesting part is initializing the table. Since it's a relatively small block that we want for the lifetime of the process, I allocate unmanaged memory for this by using Marshal.AllocHGlobal. As you can see, for maximum performance, the whole example is written as native:

readonly static byte[] msb_tab_15;

// Initialize a table of 32768 bytes with the bit position (counting from LSB=0)
// of the highest 'set' (non-zero) bit of its corresponding 16-bit index value.
// The table is compressed by half, so use (value >> 1) for indexing.
static MyStaticInit()
{
    var p = new byte[0x8000];

    for (byte n = 0; n < 16; n++)
        for (int c = (1 << n) >> 1, i = 0; i < c; i++)
            p[c + i] = n;

    msb_tab_15 = p;
}

The table requires one-time initialization via the code above. It is read-only so a single global copy can be shared for concurrent access. With this table you can quickly look up the integer log₂, which is what we're looking for here, for all the various integer widths (8, 16, 32, and 64 bits).

Notice that the table entry for 0, the sole integer for which the notion of 'highest set bit' is undefined, is given the value -1. This distinction is necessary for proper handling of 0-valued upper words in the code below. Without further ado, here is the code for each of the various integer primitives:

ulong (64-bit) Version

/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(this ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 0x40) - 1;      // handles cases v==0 and MSB==63

    int j = /**/ (int)((0xFFFFFFFFU - v /****/) >> 58) & 0x20;
    j |= /*****/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 0x10;
    return j + msb_tab_15[v >> (j + 1)];
}

uint (32-bit) Version

/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(uint v)
{
    if ((int)v <= 0)
        return (int)((v >> 26) & 0x20) - 1;     // handles cases v==0 and MSB==31

    int j = (int)((0x0000FFFFU - v) >> 27) & 0x10;
    return j + msb_tab_15[v >> (j + 1)];
}

Various overloads for the above

public static int HighestOne(long v) => HighestOne((ulong)v);
public static int HighestOne(int v) => HighestOne((uint)v);
public static int HighestOne(ushort v) => msb_tab_15[v >> 1];
public static int HighestOne(short v) => msb_tab_15[(ushort)v >> 1];
public static int HighestOne(char ch) => msb_tab_15[ch >> 1];
public static int HighestOne(sbyte v) => msb_tab_15[(byte)v >> 1];
public static int HighestOne(byte v) => msb_tab_15[v >> 1];

This is a complete, working solution which represents the best performance on .NET 4.7.2 for numerous alternatives that I compared with a specialized performance test harness. Some of these are mentioned below. The test parameters were a uniform density of all 65 bit positions, i.e., 0 ... 31/63 plus value 0 (which produces result -1). The bits below the target index position were filled randomly. The tests were x64 only, release mode, with JIT-optimizations enabled.

That's the end of my formal answer here; what follows are some casual notes and links to source code for alternative test candidates associated with the testing I ran to validate the performance and correctness of the above code.

The version provided above above, coded as Tab16A was a consistent winner over many runs. These various candidates, in active working/scratch form, can be found here, here, and here.

 1  candidates.HighestOne_Tab16A               622,496
 2  candidates.HighestOne_Tab16C               628,234
 3  candidates.HighestOne_Tab8A                649,146
 4  candidates.HighestOne_Tab8B                656,847
 5  candidates.HighestOne_Tab16B               657,147
 6  candidates.HighestOne_Tab16D               659,650
 7  _highest_one_bit_UNMANAGED.HighestOne_U    702,900
 8  de_Bruijn.IndexOfMSB                       709,672
 9  _old_2.HighestOne_Old2                     715,810
10  _test_A.HighestOne8                        757,188
11  _old_1.HighestOne_Old1                     757,925
12  _test_A.HighestOne5  (unsafe)              760,387
13  _test_B.HighestOne8  (unsafe)              763,904
14  _test_A.HighestOne3  (unsafe)              766,433
15  _test_A.HighestOne1  (unsafe)              767,321
16  _test_A.HighestOne4  (unsafe)              771,702
17  _test_B.HighestOne2  (unsafe)              772,136
18  _test_B.HighestOne1  (unsafe)              772,527
19  _test_B.HighestOne3  (unsafe)              774,140
20  _test_A.HighestOne7  (unsafe)              774,581
21  _test_B.HighestOne7  (unsafe)              775,463
22  _test_A.HighestOne2  (unsafe)              776,865
23  candidates.HighestOne_NoTab                777,698
24  _test_B.HighestOne6  (unsafe)              779,481
25  _test_A.HighestOne6  (unsafe)              781,553
26  _test_B.HighestOne4  (unsafe)              785,504
27  _test_B.HighestOne5  (unsafe)              789,797
28  _test_A.HighestOne0  (unsafe)              809,566
29  _test_B.HighestOne0  (unsafe)              814,990
30  _highest_one_bit.HighestOne                824,345
30  _bitarray_ext.RtlFindMostSignificantBit    894,069
31  candidates.HighestOne_Naive                898,865

Notable is that the terrible performance of ntdll.dll!RtlFindMostSignificantBit via P/Invoke:

[DllImport("ntdll.dll"), SuppressUnmanagedCodeSecurity, SecuritySafeCritical]
public static extern int RtlFindMostSignificantBit(ulong ul);

It's really too bad, because here's the entire actual function:

    RtlFindMostSignificantBit:
        bsr rdx, rcx  
        mov eax,0FFFFFFFFh  
        movzx ecx, dl  
        cmovne      eax,ecx  
        ret

I can't imagine the poor performance originating with these five lines, so the managed/native transition penalties must be to blame. I was also surprised that the testing really favored the 32KB (and 64KB) short (16-bit) direct-lookup tables over the 128-byte (and 256-byte) byte (8-bit) lookup tables. I thought the following would be more competitive with the 16-bit lookups, but the latter consistently outperformed this:

public static int HighestOne_Tab8A(ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 64) - 1;

    int j;
    j =  /**/ (int)((0xFFFFFFFFU - v) >> 58) & 32;
    j += /**/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 16;
    j += /**/ (int)((0x000000FFU - (v >> j)) >> 60) & 8;
    return j + msb_tab_8[v >> j];
}

The last thing I'll point out is that I was quite shocked that my deBruijn method didn't fare better. This is the method that I had previously been using pervasively:

const ulong N_bsf64 = 0x07EDD5E59A4E28C2,
            N_bsr64 = 0x03F79D71B4CB0A89;

readonly public static sbyte[]
bsf64 =
{
    63,  0, 58,  1, 59, 47, 53,  2, 60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12, 44, 24, 15,  8, 23,  7,  6,  5,
},
bsr64 =
{
     0, 47,  1, 56, 48, 27,  2, 60, 57, 49, 41, 37, 28, 16,  3, 61,
    54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11,  4, 62,
    46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
    25, 39, 14, 33, 19, 30,  9, 24, 13, 18,  8, 12,  7,  6,  5, 63,
};

public static int IndexOfLSB(ulong v) =>
    v != 0 ? bsf64[((v & (ulong)-(long)v) * N_bsf64) >> 58] : -1;

public static int IndexOfMSB(ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 64) - 1;

    v |= v >> 1; v |= v >> 2;  v |= v >> 4;   // does anybody know a better
    v |= v >> 8; v |= v >> 16; v |= v >> 32;  // way than these 12 ops?
    return bsr64[(v * N_bsr64) >> 58];
}

There's much discussion of how superior and great deBruijn methods at this SO question, and I had tended to agree. My speculation is that, while both the deBruijn and direct lookup table methods (that I found to be fastest) both have to do a table lookup, and both have very minimal branching, only the deBruijn has a 64-bit multiply operation. I only tested the IndexOfMSB functions here--not the deBruijn IndexOfLSB--but I expect the latter to fare much better chance since it has so many fewer operations (see above), and I'll likely continue to use it for LSB.

I assume your question is for an integer (called v below) and not an unsigned integer.

int v = 612635685; // whatever value you wish

unsigned int get_msb(int v)
{
    int r = 31;                         // maximum number of iteration until integer has been totally left shifted out, considering that first bit is index 0. Also we could use (sizeof(int)) << 3 - 1 instead of 31 to make it work on any platform.

    while (!(v & 0x80000000) && r--) {   // mask of the highest bit
        v <<= 1;                        // multiply integer by 2.
    }
    return r;                           // will even return -1 if no bit was set, allowing error catch
}

If you want to make it work without taking into account the sign you can add an extra 'v <<= 1;' before the loop (and change r value to 30 accordingly). Please let me know if I forgot anything. I haven't tested it but it should work just fine.

This looks big but works really fast compared to loop thank from bluegsmith

int Bit_Find_MSB_Fast(int x2)
{
    long x = x2 & 0x0FFFFFFFFl;
    long num_even = x & 0xAAAAAAAA;
    long num_odds = x & 0x55555555;

    if (x == 0) return(0);

    if (num_even > num_odds)
    {
        if ((num_even & 0xFFFF0000) != 0) // top 4
        {
            if ((num_even & 0xFF000000) != 0)
            {
                if ((num_even & 0xF0000000) != 0)
                {
                    if ((num_even & 0x80000000) != 0) return(32);
                    else
                        return(30);
                }
                else
                {
                    if ((num_even & 0x08000000) != 0) return(28);
                    else
                        return(26);
                }
            }
            else
            {
                if ((num_even & 0x00F00000) != 0)
                {
                    if ((num_even & 0x00800000) != 0) return(24);
                    else
                        return(22);
                }
                else
                {
                    if ((num_even & 0x00080000) != 0) return(20);
                    else
                        return(18);
                }
            }
        }
        else
        {
            if ((num_even & 0x0000FF00) != 0)
            {
                if ((num_even & 0x0000F000) != 0)
                {
                    if ((num_even & 0x00008000) != 0) return(16);
                    else
                        return(14);
                }
                else
                {
                    if ((num_even & 0x00000800) != 0) return(12);
                    else
                        return(10);
                }
            }
            else
            {
                if ((num_even & 0x000000F0) != 0)
                {
                    if ((num_even & 0x00000080) != 0)return(8);
                    else
                        return(6);
                }
                else
                {
                    if ((num_even & 0x00000008) != 0) return(4);
                    else
                        return(2);
                }
            }
        }
    }
    else
    {
        if ((num_odds & 0xFFFF0000) != 0) // top 4
        {
            if ((num_odds & 0xFF000000) != 0)
            {
                if ((num_odds & 0xF0000000) != 0)
                {
                    if ((num_odds & 0x40000000) != 0) return(31);
                    else
                        return(29);
                }
                else
                {
                    if ((num_odds & 0x04000000) != 0) return(27);
                    else
                        return(25);
                }
            }
            else
            {
                if ((num_odds & 0x00F00000) != 0)
                {
                    if ((num_odds & 0x00400000) != 0) return(23);
                    else
                        return(21);
                }
                else
                {
                    if ((num_odds & 0x00040000) != 0) return(19);
                    else
                        return(17);
                }
            }
        }
        else
        {
            if ((num_odds & 0x0000FF00) != 0)
            {
                if ((num_odds & 0x0000F000) != 0)
                {
                    if ((num_odds & 0x00004000) != 0) return(15);
                    else
                        return(13);
                }
                else
                {
                    if ((num_odds & 0x00000400) != 0) return(11);
                    else
                        return(9);
                }
            }
            else
            {
                if ((num_odds & 0x000000F0) != 0)
                {
                    if ((num_odds & 0x00000040) != 0)return(7);
                    else
                        return(5);
                }
                else
                {
                    if ((num_odds & 0x00000004) != 0) return(3);
                    else
                        return(1);
                }
            }
        }
    }
}

There's a proposal to add bit manipulation functions in C, specifically leading zeros is helpful to find highest bit set. See http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2827.htm#design-bit-leading.trailing.zeroes.ones

They are expected to be implemented as built-ins where possible, so sure it is an efficient way.

This is similar to what was recently added to C++ (std::countl_zero, etc).

My humble method is very simple:

MSB(x) = INT[Log(x) / Log(2)]

Translation: The MSB of x is the integer value of (Log of Base x divided by the Log of Base 2).

This can easily and quickly be adapted to any programming language. Try it on your calculator to see for yourself that it works.

Here is a fast solution for C that works in GCC and Clang; ready to be copied and pasted.

#include <limits.h>

unsigned int fls(const unsigned int value)
{
    return (unsigned int)1 << ((sizeof(unsigned int) * CHAR_BIT) - __builtin_clz(value) - 1);
}

unsigned long flsl(const unsigned long value)
{
    return (unsigned long)1 << ((sizeof(unsigned long) * CHAR_BIT) - __builtin_clzl(value) - 1);
}

unsigned long long flsll(const unsigned long long value)
{
    return (unsigned long long)1 << ((sizeof(unsigned long long) * CHAR_BIT) - __builtin_clzll(value) - 1);
}

And a little improved version for C++.

#include <climits>

constexpr unsigned int fls(const unsigned int value)
{
    return (unsigned int)1 << ((sizeof(unsigned int) * CHAR_BIT) - __builtin_clz(value) - 1);
}

constexpr unsigned long fls(const unsigned long value)
{
    return (unsigned long)1 << ((sizeof(unsigned long) * CHAR_BIT) - __builtin_clzl(value) - 1);
}

constexpr unsigned long long fls(const unsigned long long value)
{
    return (unsigned long long)1 << ((sizeof(unsigned long long) * CHAR_BIT) - __builtin_clzll(value) - 1);
}

The code assumes that value won't be 0. If you want to allow 0, you need to modify it.

Use a combination of VPTEST(D, W, B) and PSRLDQ instructions to focus in on the byte containing the most significant bit as shown below using an emulation of these instructions in Perl found at:

https://github.com/philiprbrenan/SimdAvx512

if (1) {                                                                        #TpositionOfMostSignificantBitIn64
  my @m = (                                                                     # Test strings
#B0       1       2       3       4       5       6       7
#b0123456701234567012345670123456701234567012345670123456701234567
 '0000000000000000000000000000000000000000000000000000000000000000',
 '0000000000000000000000000000000000000000000000000000000000000001',
 '0000000000000000000000000000000000000000000000000000000000000010',
 '0000000000000000000000000000000000000000000000000000000000000111',
 '0000000000000000000000000000000000000000000000000000001010010000',
 '0000000000000000000000000000000000001000000001100100001010010000',
 '0000000000000000000001001000010000000000000001100100001010010000',
 '0000000000000000100000000000000100000000000001100100001010010000',
 '1000000000000000100000000000000100000000000001100100001010010000',
);
  my @n = (0, 1, 2, 3, 10, 28, 43, 48, 64);                                     # Expected positions of msb

  sub positionOfMostSignificantBitIn64($)                                       # Find the position of the most significant bit in a string of 64 bits starting from 1 for the least significant bit or return 0 if the input field is all zeros
   {my ($s64) = @_;                                                             # String of 64 bits

    my $N = 128;                                                                # 128 bit operations
    my $f = 0;                                                                  # Position of first bit set
    my $x = '0'x$N;                                                             # Double Quad Word set to 0
    my $s = substr $x.$s64, -$N;                                                # 128 bit area needed

    substr(VPTESTMD($s, $s), -2, 1) eq '1' ? ($s = PSRLDQ $s, 4) : ($f += 32);  # Test 2 dwords
    substr(VPTESTMW($s, $s), -2, 1) eq '1' ? ($s = PSRLDQ $s, 2) : ($f += 16);  # Test 2 words
    substr(VPTESTMB($s, $s), -2, 1) eq '1' ? ($s = PSRLDQ $s, 1) : ($f +=  8);  # Test 2 bytes

    $s = substr($s, -8);                                                        # Last byte remaining

    $s < $_ ? ++$f : last for                                                   # Search remaing byte
     (qw(10000000 01000000 00100000 00010000
         00001000 00000100 00000010 00000001));

    64 - $f                                                                     # Position of first bit set
   }

  ok $n[$_] eq positionOfMostSignificantBitIn64 $m[$_] for keys @m              # Test
 }