LeetCode 201. Bitwise AND of Numbers Range(位运算)

ShenduCC

发布于 2020-02-19 10:58:14

2310

发布于 2020-02-19 10:58:14

文章被收录于专栏：算法修养算法修养

题目

题意：给你两个数n,m 0<= n<=m <=2^31-1 ，让你计算从n到m的每个数依次位与的结果。

题解：当然不能for循环，按位运算。会超时。

经过分析我们发现当一个数字为2的整次幂，比如8 ：1000，8往后位与的结果都是8，直到位与到16 ：10000，8&9&10....15 的结果是1000，再位于16的结果就是0，

也就是说如果n ~ m 如果有某个数字k ，n < k <=m ，并且k = 2^x，那么位与结果就是0，

那么如果 k <= n < m 呢？k = 2^x，其实n到m的二进制，都是在k的二进制的基础上，假设k=100...000,那么n到m 都是 100...xxxx，按照递归的思想，这个时候从n到m 减去 k，之后，又会回到第一种情况。存在某种k1 k1=2^x 使得n < k1 <=m结果为0，或者k1 <= n < m 要减k1继续重复，直到为0.

最后把减去的k,k1,k2 加起来，就是结果。

class Solution {
public:
    int a[32];
    int rangeBitwiseAnd(int m, int n) {
        
        a[0]=1;
        
        for(int i=1;i<=30;i++)
        {
            a[i]=a[i-1]*2;
        }
        
        int ans=0;
        while(1)
        {
            int x = fun(m,n);
            if(x==0)
                break;
            ans+=x;
            
            m -=x;
            n -=x;
        }
        
        return ans;
        
    }
     
    int fun(int x,int y)
    {
        for(int i=30;i>=0;i--)
        {
            if(x<a[i]&&y>=a[i])
            {
                return 0;
            }
            if(x>=a[i]&&y>=a[i])
            {
                return a[i];
            }
        }
        
        return 0;
    }
    
    
    
    
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-02-13 ，如有侵权请联系 cloudcommunity@tencent.com 删除

for循环