计算二进制整数到 0 的汉明距离的简单快捷方法？

Question

我正在写一个数独解算器，我必须计算我学到的所谓 int 到 0 的汉明距离，例如7（二进制的111）到0的汉明距离是3。所以我只是这样做：

for(int dist = 0 ; num != 0 ; num>>=1) dist += (num&1);

虽然这很好用，但我觉得有点笨拙。我试图想出一个二元运算技巧来计算距离（主要是为了好玩），但我只能找到一种适用于 1 距离的方法：

(num-1) ^ ((num<<1)-1) == num → true only if hamming dist to 0 == 1

我查看了 Whosebug 和网上，但我找不到任何东西。

假设 num 永远不会 负数并且总是小于 512，是否有一种 nicer/more 优雅的方法来评估它，也许一些二进制操作技巧？如果不是，根据上述假设，是否存在始终在误差 < 1 范围内的汉明距离的近似值？

Answer 1

要为 9 位创建查找 table（因为这是数独游戏）：

int dist[512];
dist[0] = 0;
for (i=1; i<512; i++)
    dist[i] = (i&1) + dist[i/2];

为了避免初始计算，这也可以写成记忆递归函数。

int dist(int bits) {
    static _dist[512] = {};
    if (bits == 0)
        return 0;
    else if (_dist[bits] == 0)
        _dist[bits] = (bits & 1) + dist(bits/2);
    return _dist[bits];

Answer 2

不确定，如果这有帮助，但出于好奇我通过模板实现了它：

template <int N>
struct Hamming {
    enum { value = Hamming< (N/2) >::value + (N&1)};    
};
template <>
struct Hamming<0>
{
    enum { value = 0 };
};


int main() {
    std::cout << Hamming<7>::value << std::endl;
    return 0;
}

它只能在编译时已知 N 的情况下使用，因此我认为你必须在你的情况下使用其他东西。但是，它很好地演示了如何（原则上）完全避免运行时的任何计算。

Answer 3

在java中可以使用静态方法Integer.bitCount(int i)

如果您需要其他语言的版本，这是 java 来源，应该非常容易翻译。

/**
 * Returns the number of one-bits in the two's complement binary
 * representation of the specified {@code int} value.  This function is
 * sometimes referred to as the <i>population count</i>.
 *
 * @param i the value whose bits are to be counted
 * @return the number of one-bits in the two's complement binary
 *     representation of the specified {@code int} value.
 * @since 1.5
 */
public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

计算二进制整数到 0 的汉明距离的简单快捷方法？

Simple and Quick way to calculate the hamming distance of a binary integer to 0?

c++

java

binary-operators

hamming-distance