YSMull
<-- Algorithm

Hamming Distance

原题目链接

题目描述

计算两个32位整数的Hamming distance

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

分析

问题的关键是统计一个数的二进制表示中有多少个1

  1. 遍历异或所得数的每一位,统计1的个数,判断最低位为是否是1可以用 n % 2 或者用 n & 1
    int hammingDistance(int a, int b) {
     int sum = 0;
     for (int i = 0; i < 32; i++) {
         sum += (a & 1) ^ (b & 1);
         a >>= 1;
         b >>= 1;
     }
     return sum;
    }
    
  2. 使用n & (n-1)可以消去最后一位1,判断消到0一共消了多少次。
    int hammingDistance(int a, int b) {
     int count = 0;
     int n = a ^ b;
     while(n) {
         n = n & (n-1);
         count++;
     }
     return count;
    }
    
  3. 参考 Java 里的 Integer.bitCount 方法
    public static int bitCount(int i) {
     i = i - ((i >>> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
     i = (i + (i >>> 4)) & 0x0f0f0f0f;
     i = i + (i >>> 8);
     i = i + (i >>> 16);
     return i & 0x3f;
    }