Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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.

like image 768
JHnet Avatar asked Jan 22 '14 10:01

JHnet


People also ask

How to find first set bit in a given number in C?

How to find first set bit in a given number using bitwise operator in C programming. Logic to get first set bit of a number using C program. Bitwise operators, Data types, Variables and Expressions, Basic input/output, If else, For loop Lowest order or first set bit of any number is the first bit set starting from left to right.

How to check whether a bit is set (high) or not using C?

Learn: How to check whether a bit is SET (High) or not using C programming language? Here, we will read a number and bit and check input bit is SET or not. Bitwise AND Operator (&) is used to check whether a bit is SET (HIGH) or not SET (LOW) in C and C++ programming language.

How to check the bit number of a binary bit?

Here, NUM is the number whose bit you want to check and N is the bit number, (1<<N) SET the particular bit at N th position. Example: Statement (1<<3) returns 8 (in Binary: 0000 1000 ), see the binary 3rd (count from 0 to 7) bit is SET here.

How to check if all bits of a given integer is one(1)?

Check if all the bits of a given integer is one (1) using C program: Here, we are going to implement a C program that will check whether all bits of an integer is set/one (1) or not. Problem statement: Write a C Program to check if all the bits of a given integer is one (1). Solution: We can use bitwise operator here to solve the problem.


2 Answers

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 
}
like image 146
Martin R Avatar answered Nov 03 '22 20:11

Martin R


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:

  • "Using de Bruijn Sequences to Index a 1 in a Computer Word" - Explanation about why the above code works.
like image 32
herohuyongtao Avatar answered Nov 03 '22 20:11

herohuyongtao