How to find the first bit that is different from C?

Question

I want to compare with integers in C, and the problem is to find the least significant bit that is different. What is the fastest way in C for this?

Example:

Bit 3210 ---- a = 13 (binary 1101) b = 9 (binary 1001) ^ 

The result here should be 2, because bit 2 is the first bit that is different.

Answer 1

ffs() from <strings.h> returns the position of the first set of bits, where the bits are numbered starting from 1 for the least significant bit (and ffs(0) returns zero):

 unsigned a = 0x0D; unsigned b = 0x09; unsigned x = a ^ b; int pos = ffs(x) - 1; if (pos == -1) { // a and b are equal } else { // pos is the position of the first difference } 

Answer 2

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 = a ^ b; 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]; 

Literature:

• " Using Bruijn Sequences to Index 1 in Computer Word " - An explanation of why the above code works.

Answer 3

 #include <stdint.h> int bit_count(uint32_t bits) { bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333); bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f); bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff); return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff); } int func(unsigned a, unsigned b){ unsigned x = a ^ b; return x ? bit_count((x&(-x))-1) : -1; }