比较两个二进制数并获取不同的位

Question

可能是重复的问题:
最佳算法来计算32位整数中设置位数的数量？

我想编写一个程序，以比较两个数字中1位的数量。如果我比较任意两个数字之间的位， 查找二进制数字在1和0中不同的位置。 换句话说，是异或关系。

例如，如果22（其二进制为10110）与15（其二进制为01111）进行比较

第一个：10110

第二个：01111

结果：11001

答案应该是25，但我想要得到的是3，即不同的三个1和0的数量。

- TTT

---

一些CPU具有用于人口计数的特殊硬件指令。了解编译器是否知道此事并能够发出相关代码将是有趣的。 - Kerrek SB

这被称为汉明距离。 - Potatoswatter

__builtin_popcount(22 ^ 15) = 3 __builtin_popcount(22 ^ 15) = 3 - Sazzad Hissain Khan

Answer 1

嗯，脑海中浮现的第一个非递归思路是：

int a = ...;
int b = ...;
int x = a ^ b;

int count;

for (int i = 0; i < 32; ++i) {
    if (x & (1 << i)) {
        ++count;
    }
}

- Corbin

Answer 2

std::bitset::count应该是您要查找的内容：

http://www.cplusplus.com/reference/stl/bitset/count/

http://en.cppreference.com/w/cpp/utility/bitset/count

- Ben Cottrell

---

+1. 如果你的程序花费大量时间进行这项操作，使用库函数非常重要，因为大多数微处理器都有专门的“人口计数”指令，否则很难进行可移植访问。此外，请注意 bitset 支持异或和转换为/从 unsigned long 数字。 - Potatoswatter

Answer 3

这将是最简单的方法：

int count_bits(int a)
{
    int mask;
    int count = 0;
    for (mask = 1; mask; mask <<= 1)
    {
        if (mask & a) ++count;
    }
    return count;
}

如果你想要更高级的东西，可以看看这里：http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive。

- Bartosz Moczulski