Suppose I have 2 numbers e.g. 1 and 2.Their binary representation is '01' and '10' so their bit difference is 2.For numbers 5 and 7 binary representation will be '101' and '111' so the bit difference is 1.Surely I can convert both the numbers to binary and then loop it to find the difference but is there any simpler way.??

Suppose I have 2 numbers e.g. 1 and 2.Their binary representation is '01' and '10' so their bit difference is 2.For numbers 5 and 7 binary representation will be '101' and '111' so the bit difference is 1.Surely I can convert both the numbers to binary and then loop it to find the difference but is there any simpler way.??

• javascript
• bit-manipulation

Share Follow asked May 23, 2018 at 3:19 priteshpritesh 2,1922121 silver badges2626 bronze badges

Add a ment  | 

4 Answers 4

Sorted by: Reset to default 2

You could use bitwise XOR (^) to identify the positions whose bits are different, convert the result to a string, then count up the number of occurrences of 1 in the string:

const bitDiffCount = (a, b) => {
  const bitStr = ((a ^ b) >>> 0).toString(2);
  return bitStr.split('1').length - 1;
};

console.log(bitDiffCount(5, 7));
console.log(bitDiffCount(1, 2));
console.log(bitDiffCount(16, 16));
console.log(bitDiffCount(16, 17));
console.log(bitDiffCount(16, 18));
console.log(bitDiffCount(16, 19));

Ah, a string op is an easy way to do this per CertainPerformance's answer, but here's a purely bitwise solution.

This is a flattened loop that handles JavaScript's limited 32-bit int support.

// implementation of the "bit population count" operation for 32-bit ints
function popcount(u) {
  // while I'm at it, why not break old IE support :)
  if ( !Number.isInteger(u) )
    throw new Error('Does not actually work with non-integer types.');
  // remove the above check for old IE support
  u = (u & 0x55555555) + ((u >> 1) & 0x55555555);
  u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
  u = (u & 0x0f0f0f0f) + ((u >> 4) & 0x0f0f0f0f);
  u = (u & 0x00ff00ff) + ((u >> 8) & 0x00ff00ff);
  u = (u & 0x0000ffff) + ((u >>16) & 0x0000ffff);
  return u;
}

// select all bits different, count bits
function diffcount(a, b) {
  return popcount( a ^ b );
}

// powers of two are single bits; 128 is mon, bits for 16, 32, and 8 are counted.
// 128+16 = 144, 128+32+8 = 168
console.log(diffcount(144,168)); // = 3
// -1 is 4294967295 (all bits set) unsigned
console.log(diffcount(-1,1)); // = 31
// arbitrary example
console.log(diffcount(27285120,31231992)); // = 14

If you need arbitrarily large values, let me know...

It'll require the use of typed arrays, the above functions, and a loop.

1) XOR both the numbers: x = a^b.

2) check if the XOR result is a power of 2. if it's power of 2 then there's only 1-bit difference. (x && (!(x & (x - 1)))) should be 1

bool differAtOneBitPos(unsigned int a, 
                       unsigned int b) 
{ 
    return isPowerOfTwo(a ^ b); 
}

bool isPowerOfTwo(unsigned int x) 
{ 
    return x && (!(x & (x - 1))); 
} 

You can use a bination of XOR and Brian Kernighan's algorithm for counting up bits in a binary number. I highly remend looking it up yourself. An example is shown below:

int foo( int a, int b ) {
    int c = a ^ b;
    int count;
    while( count ) {
        c &= c - 1;
        count++;
    }
    return count;
}