Finding the first bit of a set in a binary number

Question

I need to find the first bit of a set 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 to do this? Some smart way to manipulate bits?

Answer 1

If you want it to be fast, the bitcan ( bsf , bsr ) bsr or the hacking bit-twisting is the goal to go over.

EDIT: The idea of ​​using a wiring closet table to improve performance is nothing more than immature.

Answer 2

CPU

may have instructions for direct search:

Windows / MSVC:

• _ BitScanForward ()
• _ BitScanReverse ()

GCC:

• __ builtin_ffs ()
• __ builtin_ctz ()
• __ builtin_clz ()

They are usually directly compared to on-site instructions. Thus, it does not get much faster than these.

But since there are no C / C ++ functions for them, they are available only through the built-in compiler functions.

You can do it manually:

n & (n - 1) is a method of deleting the rightmost bit.

So n - (n & n - 1) will return the number with the most correct bit.

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

Alternatively, you can use a switch enclosure with all 1 << k , which will give you a solution

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

Answer 3

Bit Twiddling Hacks offers an excellent collection, er, bit twiddling hacks, with a discussion of performance / optimization. For your problem (from this site) you can use a multiple search 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 an error. For example, if the number is 0, then the loop will be infinite.

I would rewrite it as follows

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

In this case, if the number is not 0, the position (cnt) of the set bit will be counted from 1. Otherwise, the position will be 0.

Answer 5

I am not sure that the accepted answer is right. I just checked the naive loop against the solution (num and -num). They have the same speed. A 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 is my code (maybe it has some errors in the root, but I suspect that 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); }