Hamming distance - 汉明距离-蒲公英云

Hamming distance - 汉明距离

1. Hamming distance

//============================================================================
// Name        : Hamming distance
// Author      : Yongqiang Cheng
// Version     : Version 1.0.0
// Copyright   : Copyright (c) 2019 Yongqiang Cheng
// Description : Hello World in C++, Ansi-style
//============================================================================
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
int hamming_distance(const unsigned int x, const unsigned int y)
{
    int dist = 0;
    unsigned int val = x ^ y;
    // Count the number of bits set.
    while (val != 0)
    {
        // A bit is set, so increment the count and clear the bit.
        dist++;
        // val &= val - 1;
        val = val & (val - 1);
    }
    // Return the number of differing bits.
    return dist;
}
int main()
{
    unsigned int x = 1;
    unsigned int y = 4;
    int dist = hamming_distance(x, y);
    printf("dist = %d.\n", dist);
    return 0;
}
输入：x = 1, y = 4
输出：2
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
箭头指出了对应二进制位不同的位置。
dist = 2.
请按任意键继续. . .

1.1 布赖恩·克尼根算法

人类直观的计算比特为 1 的位数，跳过两个 1 之间的 0。例如 10001000，遇到最右边的 1 后，如果可以跳过中间的 0，直接跳到下一个 1，效率会高很多。这是布赖恩·克尼根位计数算法的基本思想，该算法使用特定比特位和算术运算移除等于 1 的最右比特位。

当我们在 number 和 number-1 上做 AND 位运算时，原数字 number 的最右边等于 1 的比特会被移除。基于以上思路，通过 2 次迭代就可以知道 10001000 中 1 的位数，而不需要 8 次。

在这里插入图片描述

该算法发布在 1988 年《C 语言编程第二版》的练习中 (由 Brian W. Kernighan 和 Dennis M. Ritchie 编写)。

时间复杂度： O ( 1 ) O(1) O(1)。与移位方法相似，由于整数的位数恒定，因此具有恒定的时间复杂度。但是该方法需要的迭代操作更少。
空间复杂度： O ( 1 ) O(1) O(1)，与输入无关，使用恒定大小的空间。

val & (val - 1)：将 val 的二进制表示中的最低位 1 改为 0。
val = 0b00101000 = 1 * 2^5 + 1 * 2^3 = 32 + 8 = 40
val - 1= 0b00101000 - 1 = 0b00100111 = 1 * 2^5 + 1 * 2^2 + 1 * 2^1 + 1 * 2^0 = 32 + 4 + 2 + 1 = 39
val & (val - 1) =  0b00101000 & 0b00100111 = 0b00100000