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率降序排序第一題就是這個(gè)，，立馬汗顏果然我做不出來(lái)呀！！查看了DISCUSSION，轉(zhuǎn)載如下： 方法一：
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); }}所謂的漢明距離也就是兩個(gè)二進(jìn)制數(shù)中位置上的比特不同的個(gè)數(shù)，所以可以通過(guò)異或/XOR來(lái)獲得哪些位置不同，然后count。 方法一采用向右移位31次比較最末端位來(lái)統(tǒng)計(jì)， 方法二采用Integer類(lèi)的bitcount方法直接計(jì)算。 下面分析計(jì)算bitcount的方法： - 1.首先是方法一，問(wèn)題是如果前面位都是0會(huì)帶來(lái)多余運(yùn)算，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)會(huì)使得n最右邊的1位變成0，所以可以循環(huán)直到n變成0，int bitCount(int n) { int count = 0; while (n != 0) { n &= n - 1; count++; } return count; } 還有更多的方法， 參考[這里寫(xiě)鏈接內(nèi)容](https://tech.liuchao.me/2016/11/count-bits-of-integer/)
另有java位運(yùn)算 ，`public class Test { public static void main(String[] args) { // 1、左移( << ) // 0000 0000 0000 0000 0000 0000 0000 0101 然后左移2位后，低位補(bǔ)0：// // 0000 0000 0000 0000 0000 0000 0001 0100 換算成10進(jìn)制為20 System.out.PRintln(5 << 2);// 運(yùn)行結(jié)果是20
// 2、右移( >> ) 高位補(bǔ)符號(hào)位 // 0000 0000 0000 0000 0000 0000 0000 0101 然后右移2位，高位補(bǔ)0： // 0000 0000 0000 0000 0000 0000 0000 0001 System.out.println(5 >> 2);// 運(yùn)行結(jié)果是1 // 3、無(wú)符號(hào)右移( >>> ) 高位補(bǔ)0 // 例如 -5換算成二進(jìn)制后為：0101 取反加1為1011 // 1111 1111 1111 1111 1111 1111 1111 1011 // 我們分別對(duì)5進(jìn)行右移3位、 -5進(jìn)行右移3位和無(wú)符號(hào)右移3位： System.out.println(5 >> 3);// 結(jié)果是0 System.out.println(-5 >> 3);// 結(jié)果是-1 System.out.println(-5 >>> 3);// 結(jié)果是536870911 // 4、位與( & ) // 位與：第一個(gè)操作數(shù)的的第n位于第二個(gè)操作數(shù)的第n位如果都是1，那么結(jié)果的第n為也為1，否則為0 System.out.println(5 & 3);// 結(jié)果為1 System.out.println(4 & 1);// 結(jié)果為0 // 5、位或( | ) // 第一個(gè)操作數(shù)的的第n位于第二個(gè)操作數(shù)的第n位 只要有一個(gè)是1，那么結(jié)果的第n為也為1，否則為0 System.out.println(5 | 3);// 結(jié)果為7 // 6、位異或( ^ ) // 第一個(gè)操作數(shù)的的第n位于第二個(gè)操作數(shù)的第n位 相反，那么結(jié)果的第n為也為1，否則為0 System.out.println(5 ^ 3);//結(jié)果為6 // 7、位非( ~ ) // 操作數(shù)的第n位為1，那么結(jié)果的第n位為0，反之。 System.out.println(~5);// 結(jié)果為-6 }}` 另外 & 與&&的區(qū)別就是邏輯判斷的時(shí)候，&&如果一邊不滿(mǎn)足就不判斷另一邊了
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
