算法笔记之位运算

Brian Kernighan 算法

内容：通过n&(n-1), 清除二进制n的最右边1

原理：n-1就是找到n最右边的1然后变为0，借1，同时最右边1的右边一定全是0，那么&操作之后，最右边的1变为0.

应用：Bk算法可用来求两个数的二进制公共前缀。

题目·数字范围按位与

1	给定范围[m,n],返回此范围内所有书的按位与结果。

// 解法一 寻找公共前缀
public int rangeBitwiseAnd(int m, int n) {
    int move = 0;
    while (m!=n){
        m >>= 1;
        n >>= 1;
        move++;
    }
    return m<<move;
}

// 利用BK算法 寻找最长公共前缀
public int rangeBitwiseAnd(int m, int n) {
    while (m<n){
        n &= (n-1);
    }
    return n;
}

题目·汉明距离

1	x,y的汉明距离指的是二进制不同位置的数目，计算x,y的汉明距离

// 异或之后 求1个数
public int hammingDistance(int x, int y) {
    int axr = x^y,dist = 0;
    for(int i=0;i<32;i++){
        if((axr&(1<<i))!=0) dist++;
    }
    return dist;
}

// 利用BK消除1
public int hammingDistance(int x, int y) {
    int axr = x^y;
    int dist = 0;
    while (axr!=0){
        dist++;
        axr &= (axr-1);
    }
    return dist;
}