假设我有两个数字,比如1和2。它们的二进制表示是'01'和'10',因此它们的位差为2。对于数字5和7,二进制表示将是'101'和'111',因此位差为1。当然,我可以将这两个数字转换为二进制,然后循环查找差异,但是否有更简单的方法?
假设我有两个数字,比如1和2。它们的二进制表示是'01'和'10',因此它们的位差为2。对于数字5和7,二进制表示将是'101'和'111',因此位差为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)));
}
int foo( int a, int b ) {
int c = a ^ b;
int count;
while( count ) {
c &= c - 1;
count++;
}
return count;
}
^
) 来确定二进制位不同的位置,将结果转换为字符串,然后计算字符串中 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的回答,字符串操作是一个简单的方法来完成这个任务,但这里提供了一种纯位运算的解决方案。
这是一个展开循环,处理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