leetcode 201. Bitwise AND of Numbers Range 最长公共前缀问题 + 位操作

Dear 丶 2022-06-08 09:12 126阅读 0赞

Given a range \[m, n\] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range \[5, 7\], you should return 4.

这道题最自觉的做法就是循环做位and操作，但是我在网上看到了一个做法， 想法很棒，这道题可以直接转化为另一个问题：再一串连续的数组中，寻找他们的公共前缀。

直接暴力去计算可能要超时

代码如下：

/*
     * 这道题考察的是位运算的使用
     * 那么这道题其实并不难，我们先从题目中给的例子来分析，
     * [5, 7]里共有三个数字，分别写出它们的二进制为：
     * 101　　110　　111
     * 相与后的结果为100，仔细观察我们可以得出，最后的数是该数字范围内所有的数的左边共同的部分，
     * 如果上面那个例子不太明显，我们再来看一个范围[26, 30]，它们的二进制如下：
     * 11010　　11011　　11100　　11101　　11110
     * 
     * 那么本题就可以转化为另一个问题，直接找一串连续数字的公共前缀
     * 
     * */
    public class Solution 
    {
        public int rangeBitwiseAnd(int m, int n) 
        {
            int i=0;
            while(m!=n)
            {
                m=m>>1;
                n=n>>1;
                i++;
            }
            return (m<<i);
        }
    
    
        /*
         * 这是直接做或操作，但是可能超时
         * */
        public int rangeBitwiseAndByLoop(int m, int n) 
        {
            int res=m;
            for(int i=m+1;i<=n;i++)
                res &=i;
            return res;
        }
    }

下面是C++的做法，这道题肯定是用位运算来组，最直接的做法就是循环遍历去做，但是会超时，后来网上发现了一个寻找公共前缀的做法，很棒

代码如下：

#include <iostream>
    #include <vector>
    #include <string>
    #include <map>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <algorithm>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int rangeBitwiseAnd(int m, int n) 
        {
            int i = 0;
            while (m != n)
            {
                m = m >> 1;
                n = n >> 1;
                i++;
            }
            return m << i;
        }
    };