2

我正在写一个数独求解器，我必须计算我学到的被称为intto0的汉明距离，例如7（111二进制） to的汉明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

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

假设它num永远不是负数并且总是小于512，是否有更好/更优雅的方式来评估它，也许是一些二元运算技巧？如果不是，鉴于上述假设，汉明距离的近似值是否总是在误差范围内< 1？

4

3 回答 3

2

要为 9 位创建一个查找表（因为这是用于数独）：

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];
于 2016-03-14T18:16:11.653 回答
1

在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;
}
于 2016-03-14T18:29:01.337 回答
0

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

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 时才能使用它，因此我认为您将不得不在您的情况下使用其他东西。然而，它很好地展示了如何（原则上）完全避免运行时的任何计算。

于 2016-03-14T18:24:01.547 回答