Getting the number of trailing 1 bits

Question

Are there any efficient bitwise operations I can do to get the number of set bits that an integer ends with? For example 11₁₀ = 1011₂ would be two trailing 1 bits. 8₁₀ = 1000₂ would be 0 trailing 1 bits.

Is there a better algorithm for this than a linear search? I'm implementing a randomized skip list and using random numbers to determine the maximum level of an element when inserting it. I am dealing with 32 bit integers in C++.

Edit: assembler is out of the question, I'm interested in a pure C++ solution.

Answer 1

Calculate ~i & (i + 1) and use the result as a lookup in a table with 32 entries. 1 means zero 1s, 2 means one 1, 4 means two 1s, and so on, except that 0 means 32 1s.

Answer 2

The Bit Twiddling Hacks page has a number of algorithms for counting trailing zeros. Any of them can be adapted by simply inverting your number first, and there are probably clever ways to alter the algorithms in place without doing that as well. On a modern CPU with cheap floating point operations the best is probably thus:

unsigned int v=~input;            // find the number of trailing ones in input
int r;                     // the result goes here
float f = (float)(v & -v); // cast the least significant bit in v to a float
r = (*(uint32_t *)&f >> 23) - 0x7f;
if(r==-127) r=32;

Answer 3

Taking the answer from Ignacio Vazquez-Abrams and completing it with the count rather than a table:

b = ~i & (i+1);   // this gives a 1 to the left of the trailing 1's
b--;              // this gets us just the trailing 1's that need counting
b = (b & 0x55555555) + ((b>>1) & 0x55555555);  // 2 bit sums of 1 bit numbers
b = (b & 0x33333333) + ((b>>2) & 0x33333333);  // 4 bit sums of 2 bit numbers
b = (b & 0x0f0f0f0f) + ((b>>4) & 0x0f0f0f0f);  // 8 bit sums of 4 bit numbers
b = (b & 0x00ff00ff) + ((b>>8) & 0x00ff00ff);  // 16 bit sums of 8 bit numbers
b = (b & 0x0000ffff) + ((b>>16) & 0x0000ffff); // sum of 16 bit numbers

at the end b will contain the count of 1's (the masks, adding and shifting count the 1's). Unless I goofed of course. Test before use.

Answer 4

GCC has __builtin_ctz and other compilers have their own intrinsics. Just protect it with an #ifdef:

#ifdef __GNUC__
int trailingones( uint32_t in ) {
    return ~ in == 0? 32 : __builtin_ctz( ~ in );
}
#else
// portable implementation
#endif

On x86, this builtin will compile to one very fast instruction. Other platforms might be somewhat slower, but most have some kind of bit-counting functionality that will beat what you can do with pure C operators.

Answer 5

There may be better answers available, particularly if assembler isn't out of the question, but one viable solution would be to use a lookup table. It would have 256 entries, each returning the number of contiguous trailing 1 bits. Apply it to the lowest byte. If it's 8, apply to the next and keep count.

Answer 6

Implementing Steven Sudit's idea...

uint32_t n; // input value
uint8_t o;  // number of trailing one bits in n

uint8_t trailing_ones[256] = {
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 8};

uint8_t t;
do {
  t=trailing_ones[n&255];
  o+=t;
} while(t==8 && (n>>=8))

1 (best) to 4 (worst) (average 1.004) times (1 lookup + 1 comparison + 3 arithmetic operations) minus one arithmetic operation.

Answer 7

This code counts the number of trailing zero bits, taken from here (there's also a version that depends on the IEEE 32 bit floating point representation, but I wouldn't trust it, and the modulus/division approaches look really slick - also worth a try):

int CountTrailingZeroBits(unsigned int v) // 32 bit
{
    unsigned int c = 32; // c will be the number of zero bits on the right

    static const unsigned int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
    static const unsigned int S[] = {1, 2, 4, 8, 16}; // Our Magic Binary Numbers

    for (int i = 4; i >= 0; --i) // unroll for more speed
    {
        if (v & B[i])
        {
            v <<= S[i];
            c -= S[i];
        }
    }

    if (v)
    {
        c--;
    }

    return c;
}

and then to count trailing ones:

int CountTrailingOneBits(unsigned int v)
{
    return CountTrailingZeroBits(~v);
}

Answer 8

Blazingly fast ways to find the number of trailing 0's are given in Hacker's Delight.

You could complement your integer (or more generally, word) to find the number of trailing 1's.

Answer 9

http://graphics.stanford.edu/~seander/bithacks.html might give you some inspiration.

Answer 10

Implementation based on Ignacio Vazquez-Abrams's answer

uint8_t trailing_ones(uint32_t i) {
 return log2(~i & (i + 1));
}

Implementation of log2() is left as an exercise for the reader (see here)

Answer 11

Taking @phkahler's answer you can define the following preprocessor statement:

#define trailing_ones(x) __builtin_ctz(~x & (x + 1))

As you get a one left to all the prior ones, you can simply count the trailing zeros.

Answer 12

I have this sample for you :

#include <stdio.h>

int trailbits ( unsigned int bits, bool zero )
{
    int bitsize = sizeof(int) * 8;
    int len = 0;
    int trail = 0;
    unsigned int compbits = bits;

    if ( zero ) compbits = ~bits;

    for ( ; bitsize; bitsize-- )
    {
        if ( compbits & 0x01 ) trail++;
        else
        {
            if ( trail > 1 ) len++;
            trail = 0;
        }
        compbits = compbits >> 1;
    }

    if ( trail > 1 ) len++;

    return len;
}

void PrintBits ( unsigned int bits )
{
    unsigned int pbit = 0x80000000;
    for ( int len=0 ; len<32; len++ )
    {
        printf ( "%c ", pbit & bits ? '1' : '0' ); 
        pbit = pbit >> 1;
    }
    printf ( "\n" );
}

void main(void)
{
    unsigned int forbyte = 0x0CC00990;

    PrintBits ( forbyte );

    printf ( "Trailing ones is %d\n", trailbits ( forbyte, false ));
    printf ( "Trailing zeros is %d\n", trailbits ( forbyte, true ));
}