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率降序排序第一題就是這個，，立馬汗顏果然我做不出來呀?。〔榭戳薉ISCUSSION，轉載如下： 方法一：
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 - 1 | 1 0 1 1 1 1 1
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 }}` 另外 & 與&&的區別就是邏輯判斷的時候，&&如果一邊不滿足就不判斷另一邊了
新聞熱點
疑難解答
