[Leetcode][第461题][JAVA][汉明距离][位运算][Brian Kernighan]

缺乏、安全感 2022-11-30 04:12 142阅读 0赞

#### 【问题描述】\[简单\] ####

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

#### 【解答思路】 ####

###### 1. 内置位计数功能 ######

**时间复杂度：O(1) 空间复杂度：O(1)**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

class Solution { 
        public int hammingDistance(int x, int y) { 
            return Integer.bitCount(x ^ y); 
        }
    }

###### 2. 移位 ######

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

**时间复杂度：O(1) 空间复杂度：O(1)**

class Solution { 
      public int hammingDistance(int x, int y) { 
        int xor = x ^ y;
        int distance = 0;
        while (xor != 0) { 
          if (xor % 2 == 1)
            distance += 1;
          xor = xor >> 1;
        }
        return distance;
      }
    }

###### 3. 布赖恩·克尼根算法 Brian Kernighan ######

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

**时间复杂度：O(1) 空间复杂度：O(1)**  
![在这里插入图片描述][2020082311150564.png_pic_center]

class Solution { 
      public int hammingDistance(int x, int y) { 
        int xor = x ^ y;
        int distance = 0;
        while (xor != 0) { 
          distance += 1;
          // remove the rightmost bit of '1'
          xor = xor & (xor - 1);
        }
        return distance;
      }
    }

#### 【总结】 ####

###### 1. 汉明距离 ######

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

###### 2. 位运算 ######

**异或运算（^）**  
运算规则：0^0=0； 0^1=1； 1^0=1； 1^1=0；  
即：参加运算的两个对象，如果两个相应位为“异”（值不同），则该位结果为1，否则为0。  
5 ^ 1 = 0101 ^ 0001 = 0100 = 4  
5 ^ 3 = 0101 ^ 0011 = 0110 = 6  
用法

1.  翻转指定位 对应位异或1  
    X=10101110，使X低4位翻转，用X ^0000 1111 = 1010 0001即可得到。
2.  两个数是否相等 ==0  
    5 ^ 5 = 0101 ^ 0101 = 0000 = 0

**与运算（&）**  
运算规则：0&0=0; 0&1=0; 1&0=0; 1&1=1;  
即：两位同时为“1”，结果才为“1”，否则为0  
5 & 1 = 0101 & 0001 = 0001 = 1  
5 & 2 = 0101 & 0010 = 0000 = 0  
用法  
取指定位 对应位与1  
设X=10101110，  
取X的低4位，用 X & 0000 1111 = 00001110 即可得到；

**或运算（|）**  
运算规则：0|0=0； 0|1=1； 1|0=1； 1|1=1；  
即 ：参加运算的两个对象只要有一个为1，其值为1  
用法：  
指定位置置1 对应位或1  
将X=10100000的低4位置1 ，用X | 0000 1111 = 1010 1111即可得到

**取反运算（~）**  
运算规则：~1=0； ~0=1；  
即：对一个二进制数按位取反，即将0变1，1变0

**带符号左移运算（<<）**  
若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2(右边补0)  
3 << 1 = 0011 <<1 = 0110 = 6  
**带符号右移运算（>>）**  
正数操作数每右移一位，相当于该数除以2  
(左补0 or 补1得看被移数是正还是负)  
5 >> 1 = 0101 >> 1 = 0010 = 2  
5 >> 2 = 0101 >> 2 = 0001 = 1  
\-14 >> 2 = 11110010 >> 2 = 11111100 = -4  
**无符号右移运算（>>>）**  
5 >>> 1 = 0101 >>> 1 = 0010 = 2  
\-14 >>>2 =11111111 11111111 1111111111110010 >>>2 = 00111111 11111111 1111111111111100 = 1073741820  
**移位总结**

*  正数的左移与右移，负数的无符号右移，就是相应的补码移位所得，在高位补0即可。
 *  负数的右移，就是补码高位补1,然后按位取反加1即可。

###### 3. 位运算 判相等换位异或^ 取位与&1 置位或|1 ######

###### 4. Brian Kernighan算法 ######

n&(n-1) //n二进制最右位的 1 置 0

相关题目Brian Kernighan算法  
[\[Leetcode\]\[第201题\]\[JAVA\]\[数字范围按位与\]\[位运算\]\[Brian Kernighan\]][Leetcode_201_JAVA_Brian Kernighan]

转载链接：https://leetcode-cn.com/problems/hamming-distance/solution/yi-ming-ju-chi-by-leetcode/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/7b02a22a9c6149c0b930dc47e539f540.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/28de59dd29c549599062aafd63a75370.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/026d9e37889447a4a2532507177b01e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/9dde56a9088d4286a7790d0e83ed9d5c.png
[2020082311150564.png_pic_center]: /images/20221124/32f9d565920a4323a8aed19410538def.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221124/d921f50aabbf4bb8810fc6202d95830d.png
[Leetcode_201_JAVA_Brian Kernighan]: https://blog.csdn.net/dadongwudi/article/details/108180384