BrianKernighan算法

1.BrianKernighan算法概述

        BrianKernighan算法是一种用于计算整数二进制中1的个数（汉明重量）的算法，通过逐次清除最低位的1来减少不必要的循环次数，从而提高计算效率；

        其原理就是通过 n 与 n-1 进行与操作，从而消除最低位的1，并通过循环计数记录1的个数；

public static int countSetBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

        BrianKernighan算法其中 n 与 n-1 进行与操作引申出来 n 与 n 的补码进行与操作得到最低位的1，该操作在很多算法中有着较为精妙的应用；

2.BrianKernighan算法相关应用算法

2.1 2的幂

231. 2 的幂 - 力扣（LeetCode）

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n>0 && n == (n&(-n));
    }
}

• 观察所有2的幂次方的二进制格式就会发现，他们只有一个1；
• 如果n为2的幂次方，那他必定与最低位的1相等；

2.2 只出现一次的数字 III

260. 只出现一次的数字 III - 力扣（LeetCode）

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按任意顺序返回答案。

class Solution {
    public int[] singleNumber(int[] nums) {
        int length = nums.length;
        int eor1 = 0, eor2 = 0, temp = 0;
        for (int i = 0; i < length; i++){
            eor1 ^= nums[i];
        }
        temp = (-eor1) & eor1;
        for (int i = 0; i < length; i++){
            if ((temp & nums[i]) == 0){
                eor2 ^= nums[i];
            }
        }
        return new int[]{eor2,eor1^eor2};
    }
}

• 利用异或（^）的性质：一个数异或自己得0；
• 这样将数组中的数依次异或完就只剩下两个只出现一次的元素；
• 这时候剩下的 eor1 中为1的便只能是元素一与元素二不同的位，直接获取其最低位1，跟据该位为1还是为0就可以将数组分成两组，一组含有元素一，一组含有元素二，再将其中一组异或起来就得到其中一个元素；
• 最后将得到的元素同 eor1 相异或就得到了另一个元素；

2.3 数字范围按位与

201. 数字范围按位与 - 力扣（LeetCode）

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

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        while (right > left){
            right -= right & (-right);
        }
        return right;
    }
}

• 由于与的性质，区间内的数字的任意一位只要为0那么所有数字按位与的该位就为0；
• 区间中的数字又是相邻的，能留存下1的只有 left 与 right 共有的前缀1；
• 他们的共有前缀可以通过 right 不断消去低位1直至同left相同或小于left（无公共前缀）；