如何在Javascript中找到两个数字之间的位差

Question

假设我有两个数字，比如1和2。它们的二进制表示是'01'和'10'，因此它们的位差为2。对于数字5和7，二进制表示将是'101'和'111'，因此位差为1。当然，我可以将这两个数字转换为二进制，然后循环查找差异，但是否有更简单的方法？

- pritesh

Answer 1

1）对这两个数字进行异或操作：x = a^b。

2）检查异或结果是否为2的幂。如果是2的幂，则只有1位不同。(x && (!(x & (x - 1))))应该为1。

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

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

- GorvGoyl

Answer 2

您可以使用XOR和Brian Kernighan算法来计算二进制数字中的位数。我强烈建议您自己查找相关信息。以下是一个示例：

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

- Holden

Answer 3

你可以使用按位异或 (^) 来确定二进制位不同的位置，将结果转换为字符串，然后计算字符串中 1 的出现次数来解决问题：

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));

- CertainPerformance

---

转换为字符串，分割字符串，全部计数一些位。至少它很简单。 - TylerY86

Answer 4

啊，根据CertainPerformance的回答，字符串操作是一个简单的方法来完成这个任务，但这里提供了一种纯位运算的解决方案。

这是一个展开循环，处理JavaScript有限的32位整数支持。

// 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 common, 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

如果您需要任意大的值，请告诉我...

这将需要使用类型化数组、上述函数和循环。

（注意：保留HTML标签，不做解释）

- TylerY86

---

你询问了位差异，你标记了这个问题为位操作。简单是主观的。如果将其转换为字符串符合你的口味，我只能摇头。 - TylerY86