公共前缀与Brian Kernighan 算法

问题描述

数字范围按位与
给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）

分析题目可知，我们只要寻找到两个数的公共前缀部分，即可求解。

目前有一个普通的解法，即使用right shift的bitwise方法来消除除了公共前缀的所有位数，并将结果在补零补齐输出即可。
该方法的代码如下：

1
2
3
4
5
6
7
8
9
public int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while(m<n){
            m = m>>1;
            n = n>>1;
            shift++;
        }
        return m<<shift;
    }

Brian Kernighan 算法

除了一般的解法，我们可以使用一种特殊的位运算来求解。这便是Brian Kernighan 算法的关键之处。
$n^(n-1)$即可将n最右的非零（1）翻转为0。这样也与right shift的方法异曲同工。当$n<=m$的时候，我们可以认为其非公共前缀部分以及全部翻转，那么我们直接返回n即可求解。

相关代码

1
2
3
4
5
6
public int rangeBitwiseAnd(int m, int n) {
        while(m<n){
            n = n&(n-1);
        }
        return n;
    }

后续

我们再看一题Leetcode 461 汉明距离，题目描述如下：

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：
0 ≤ x, y < 231.

我们可以使用异或运算来得到二进制位的不同，那么如何计算不同位置的数目呢？我们同样可以使用Brain Kernighan算法将异或运算的结果$k=k&(k-1)$直到其为零。这样就可以计算具体数目了。

代码如下：

1
2
3
4
5
6
7
8
9
public int hammingDistance(int x, int y) {
        int t = x^y;
        int c = 0;
        while(t>0){
            c++;
            t = t&(t-1);
        }
        return c;
    }

感兴趣的读者可以参考下述的材料。它会对bitwise operation有更深入的介绍。

参考材料：

java
算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！