Brian Kernighan算法得名于计算机科学家Brian Kernighan，他是贝尔实验室的一位著名计算机科学家，曾与Dennis Ritchie共同开发了C语言。

基本介绍

Brian Kernighan算法的起源可以追溯到1970年代早期，当时计算机的存储容量非常有限，人们对于优化代码和节省内存空间的需求非常迫切。在那个时候，统计一个整数的二进制表示中有多少个位为1是一个常见的需求，例如在计算机中检查错误、位掩码操作等场景中。

Brian Kernighan提出了一种高效的位计数算法，即后来以他的名字命名的Brian Kernighan算法。这个算法通过运用位操作和二进制数学的技巧，以一种更加高效的方式统计一个整数的二进制表示中1的个数。

该算法的基本思想是利用整数num与num-1进行按位与操作（num & (num - 1)），这个操作可以将num的二进制表示中最右边的1变为0。通过重复这个操作直到num变为0，就可以统计出二进制表示中1的个数。

虽然算法比较简单，但是比较经典

JAVA实现如下

public int countOnes(int x) {
    int ones = 0;
    while (x > 0) {
        x &= (x - 1);
        ones++;
    }
    return ones;
}

其他运用

汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

解题思路

二进制数只有01,异或操作相同为0,不同为1,我们使用异或操作不同的位置就变成1,数1的个数就为不同的个数

先进行异或操作，在执行Brian Kernighan算法

JAVA实现

func hammingDistance(x int, y int) int {  
 x ^= y//异或  
 y = 0  
 for x > 0 {//数1Brian Kernighan算法  
  x ^= x - 1  
  y++  
 }  
 return y  
}

数字范围按位与

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

 

示例 1：

输入： left = 5, right = 7
输出： 4

解题思路

对于给定的范围 [m,n]（m<n），我们可以对数字 n 迭代地应用上述技巧，清除最右边的 1，直到它小于或等于 m，此时非公共前缀部分的 1 均被消去。因此最后我们返回 n 即可。

JAVA实现

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        while (m < n) {
            // 抹去最右边的 1
            n = n & (n - 1);
        }
        return n;
    }
}