finding the first set bit in a binary number

Question

I need to find the first set bit in a binary number from right to left; I came up with this solution:

int cnt=0;
while (number& 1 ==0)
{
    cnt++;
    number>>=1;
}

Is there a better way of doing it? Some clever bit manipulation technique?

Answer 1

processor may have instruction to find that directly:

Windows/MSVC:

• _BitScanForward()
• _BitScanReverse()

GCC:

• __builtin_ffs()
• __builtin_ctz()
• __builtin_clz()

These typically map directly to native hardware instructions. So it doesn't get much faster than these.

But since there's no C/C++ functionality for them, they're only accessible via compiler intrinsics.

You can do it manually that way:

n & (n - 1) is a technique to remove the rightmost set bit.

So, n - (n & n - 1) will return a number with only the rightmost set bit.

then a 'log2' of the result give the solution: this link may help

You may alternatively use a switch case with all 1 << k will give you the solution

switch (n - (n & n - 1)) {
    case 0: ...
    case 1 << 0: return 0;
    case 1 << 1: return 1;
    ...
}

Answer 2

If you want it to be fast, bitscan instruction (bsf, bsr) or bit-twiddling hack is the target to go.

EDIT: The idea of using switch-case table to improve performance is nothing but immature.

Answer 3

Bit Twiddling Hacks offers an excellent collection of, er, bit twiddling hacks, with performance/optimisation discussion attached. For your problem (from that site), you can use multiply-and-lookup strategy:

unsigned int c = number;  // your input number
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[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
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((c & -c) * 0x077CB531U)) >> 27];

Answer 4

Your code

int cnt=0;
   while (number& 1 ==0)
   {
       cnt++;
       number>>=1;
   }

has a bug. For example if number is equal to 0 then the loop will be infinite.

I would rewrite it the following way

int cnt = 0;
if ( number ) while ( !( number & ( 1 << cnt++ ) ) );

In this case if number is not equal to 0 then the position (cnt) of the set bit will be count starting from 1. Otherwise the position will be equal to 0.

Answer 5

I'm not sure the accepted answer is right. I just tested the naive loop versus the (num & -num) solution. They are both the same speed. The naive loop is much less code. I built with:

gcc 4.7.2 from MinGW, on Win 7 gcc test.c -o test.exe -std=c99 -Wall -O2

Here's my code (it probably has some corner case bugs, but I suspect the timings are roughly valid).

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NUM_NUMS 65536


int find_first_bits(unsigned nums[NUM_NUMS])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < 10000; j++) {
        for (int i = 0; i < NUM_NUMS; i++) {
            switch (nums[i] & -nums[i]) {
                case (1<<0): total += 1; break;
                case (1<<1): total += 2; break;
                case (1<<2): total += 3; break;
                case (1<<3): total += 4; break;
                case (1<<4): total += 5; break;
                case (1<<5): total += 6; break;
                case (1<<6): total += 7; break;
                case (1<<7): total += 8; break;
                case (1<<8): total += 9; break;
                case (1<<9): total += 10; break;
                case (1<<10): total += 11; break;
                case (1<<11): total += 12; break;
                case (1<<12): total += 13; break;
                case (1<<13): total += 14; break;
                case (1<<14): total += 15; break;
                case (1<<15): total += 16; break;
                case (1<<16): total += 17; break;
                case (1<<17): total += 18; break;
                case (1<<18): total += 19; break;
                case (1<<19): total += 20; break;
                case (1<<20): total += 21; break;
                case (1<<21): total += 22; break;
                case (1<<22): total += 23; break;
                case (1<<23): total += 24; break;
                case (1<<24): total += 25; break;
                case (1<<25): total += 26; break;
                case (1<<26): total += 27; break;
                case (1<<27): total += 28; break;
                case (1<<28): total += 29; break;
                case (1<<29): total += 30; break;
                case (1<<30): total += 31; break;
                case (1<<31): total += 32; break;
            }
        }
    }

    return total;
}


int find_first_bits2(unsigned nums[NUM_NUMS])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < 10000; j++) {
        for (int i = 0; i < NUM_NUMS; i++) {
            unsigned mask = 1;
            for (int cnt = 1; cnt <= 32; cnt++, mask <<= 1) {
                if (nums[i] & mask) {
                    total += cnt;
                    break;
                }
            }
        }
    }

    return total;
}


int main() {
    // Create some random data to test
    unsigned nums[NUM_NUMS];
    for (int i = 0; i < NUM_NUMS; i++) {
        nums[i] = rand() + (rand() << 15);
    }

    clock_t start_time, end_time;
    int result;

    start_time = clock();
    result = find_first_bits(nums);
    end_time = clock();
    printf("Time = %.5f, result = %d\n", (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits2(nums);
    end_time = clock();
    printf("Time = %.5f, result = %d\n", (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
}