Hamming distance - 汉明距离

客官°小女子只卖身不卖艺 2022-10-25 14:02 187阅读 0赞

# **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 次。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_centet]

该算法发布在 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

## References ##

[https://leetcode-cn.com/][https_leetcode-cn.com]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_centet]: /images/20221024/843fd5ce78eb4272a0b90111ab176e09.png
[https_leetcode-cn.com]: https://leetcode-cn.com/