461. Hamming Distance

2019-11-09 20:51:39

字体：大中小

来源：转载

供稿：网友

461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note: 0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑

The above arrows point to positions where the corresponding bits are different. 以AC率降序排序第一题就是这个，，立马汗颜果然我做不出来呀！！查看了DISCUSSION，转载如下： 方法一：

public int hammingDistance(int x, int y) { int xor = x ^ y, count = 0; for (int i=0;i<32;i++) count += (xor >> i) & 1; return count;}

方法二：

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

所谓的汉明距离也就是两个二进制数中位置上的比特不同的个数，所以可以通过异或/XOR来获得哪些位置不同，然后count。方法一采用向右移位31次比较最末端位来统计，方法二采用Integer类的bitcount方法直接计算。 下面分析计算bitcount的方法： - 1.首先是方法一，问题是如果前面位都是0会带来多余运算，naive。 - 2.然后,optimized naive way int bitCount(int n) { int count = 0; while (n != 0) { count += n & 1; n >>= 1; } return count; } - 3.Brian Kernighan’s way - n & (n – 1) will clear the last significant bit set, e.g. n = 112

` n | 1 1 1 0 0 0 0 n - 1 | 1 1 0 1 1 1 1

n &= n - 1 | 1 1 0 0 0 0 0

n | 1 1 0 0 0 0 0

n - 1 | 1 0 1 1 1 1 1

n &= n - 1 | 1 0 0 0 0 0 0

n | 1 0 0 0 0 0 0

n - 1 | 0 1 1 1 1 1 1 n &= n - 1 | 0 0 0 0 0 0 0 具体思想就是n&(n-1)会使得n最右边的1位变成0，所以可以循环直到n变成0，int bitCount(int n) { int count = 0; while (n != 0) { n &= n - 1; count++; } return count; } 还有更多的方法，参考[这里写链接内容](https://tech.liuchao.me/2016/11/count-bits-of-integer/)

另有java位运算 ，`public class Test { public static void main(String[] args) { // 1、左移( << ) // 0000 0000 0000 0000 0000 0000 0000 0101 然后左移2位后，低位补0：// // 0000 0000 0000 0000 0000 0000 0001 0100 换算成10进制为20 System.out.PRintln(5 << 2);// 运行结果是20

// 2、右移( >> ) 高位补符号位 // 0000 0000 0000 0000 0000 0000 0000 0101 然后右移2位，高位补0： // 0000 0000 0000 0000 0000 0000 0000 0001 System.out.println(5 >> 2);// 运行结果是1 // 3、无符号右移( >>> ) 高位补0 // 例如 -5换算成二进制后为：0101 取反加1为1011 // 1111 1111 1111 1111 1111 1111 1111 1011 // 我们分别对5进行右移3位、 -5进行右移3位和无符号右移3位： System.out.println(5 >> 3);// 结果是0 System.out.println(-5 >> 3);// 结果是-1 System.out.println(-5 >>> 3);// 结果是536870911 // 4、位与( & ) // 位与：第一个操作数的的第n位于第二个操作数的第n位如果都是1，那么结果的第n为也为1，否则为0 System.out.println(5 & 3);// 结果为1 System.out.println(4 & 1);// 结果为0 // 5、位或( | ) // 第一个操作数的的第n位于第二个操作数的第n位只要有一个是1，那么结果的第n为也为1，否则为0 System.out.println(5 | 3);// 结果为7 // 6、位异或( ^ ) // 第一个操作数的的第n位于第二个操作数的第n位相反，那么结果的第n为也为1，否则为0 System.out.println(5 ^ 3);//结果为6 // 7、位非( ~ ) // 操作数的第n位为1，那么结果的第n位为0，反之。 System.out.println(~5);// 结果为-6 }

}` 另外 & 与&&的区别就是逻辑判断的时候，&&如果一边不满足就不判断另一边了

上一篇：可调闹钟的时钟

下一篇：116. Populating Next Right Pointers in Each Node