布赖恩·克尼根位计数算法说明及简单使用

x33g5p2x  于10个月前 转载在 其他  
字(0.4k)|赞(0)|评价(0)|浏览(96)

1,算法说明

一个数 number,若对 number 与 number-1 做与运算,即 number&(number-1) 时,则number的 二进制表示中最右边为 1 的位会被置零。

例如:number = 44,其二进制为 101100

number = number&(number-1) = 40, 其二进制为 101000,最右边的 1 被置零;
number = number&(number-1) = 32, 其二进制为100000,最右边的 1 被置零;
number = number&(number-1) = 0, 所有的 1 都被置零。

2,例题

解答:

public int hammingDistance(int x, int y) {
    int t = x ^ y;
    int distance = 0;
    while (t!= 0) {
      distance += 1;
      t = t & (t - 1);
    }
    return distance;
  }

相关文章