CODEWITHSUNDEEP
cbit-manipulation
JHnet
JHnet

Reputation: 471

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

I want to compare to Integers in C and the problem is to find the least significant bit that is different. What is the fastest way in C to do 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.

Upvotes: 7

Views: 2242

Answers (3)

herohuyongtao
herohuyongtao

Reputation: 50657

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 = 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];

References:

Upvotes: 3

BLUEPIXY
BLUEPIXY

Reputation: 40145

#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;
}

Upvotes: 2

Martin R
Martin R

Reputation: 539695

ffs() from <strings.h> returns the position of the first bit set, where the bits are numbered starting at 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 
}

Upvotes: 9

Related Questions