位运算：Brian Kernighan算法应用

概念介绍

Brian Kernighan算法可以用于清除二进制数中最右侧的1。Brian Kernighan算法的做法是先将当前数减一，然后在与当前数进行按位与运算。

x=x&(x-1)

利用此算法我们可以统计一个数字的二进制中的1的个数，即一比特数：

java

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

c/c++

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

python

def countOnes(x: int) -> int:
    ones = 0
    while x > 0:
        x &= (x - 1)
        ones += 1
    return ones

Go

func onesCount(x int) (ones int) {
    for ; x > 0; x &= x - 1 {
        ones++
    }
    return
}

原文链接: https://www.yukx.com/arithmetic/article/details/2394.html 优科学习网位运算：Brian Kernighan算法应用