专栏首页算法修养LeetCode 201. Bitwise AND of Numbers Range(位运算)

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

题目

题意:给你两个数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;
    }
    
    
    
    
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1585 Check If String Is Transformable With Substring Sort Operations

    题意:一个只有0-9组成的字符串,每次选择任意一个子串,按照数字从小到大排序。问从源字符串能否经过若干次操作转换成目标字符串。

    ShenduCC
  • HDU 5157 Harry and magic string(回文树)

    Harry and magic string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: ...

    ShenduCC
  • 天梯赛 大区赛 L3-014.周游世界 (Dijkstra)

    L3-014. 周游世界 时间限制 200 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standar...

    ShenduCC
  • 2013年第四届蓝桥杯C/C++B组省赛题目解析

    Zoctopus
  • 经典算法学习之回溯法

    回溯法的应用范围:只要能把待求解的问题分成不太多的步骤,每个步骤又只有不太多的选择就可以考虑使用回溯法。  若用回溯法求问题的所有解时,要回溯到根,且根结点的所...

    用户1215536
  • P2015 二叉苹果树 树状dp

    用户2965768
  • HDU-5584-LCM Walk

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> using namespace std; int gcd(in...

    f_zyj
  • LeetCode 1585 Check If String Is Transformable With Substring Sort Operations

    题意:一个只有0-9组成的字符串,每次选择任意一个子串,按照数字从小到大排序。问从源字符串能否经过若干次操作转换成目标字符串。

    ShenduCC
  • BUPT2017 wintertraining(15) #2 题解

    ​ 因为2520%pre_lcm0,所以x%pre_lcm(x%2520)%pre_lcm

    饶文津
  • P1036 选数

    杨鹏伟

扫码关注云+社区

领取腾讯云代金券