leetcode 201 数字范围按位与

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

解法：若是按位的操作，我们多是先考虑位运算。

那么我们可以考虑同一bit位下所有的数字都是为1，若是都为1，则答案也必然为1。

很明显，我们能发现同一bit位下，1和0都是有周期的，比如最低位总是01010101（数字从0开始）。

可以得出，假设某一位为第i位，那么该位的周期(设i是从0开始)就是1<<(i+1),那么总是先出现1<<i个0，然后再出现1<<i个1。

所以我们可以检查一下m和n是不是在半个周期内，若不是，则必然为0，直接跳过。

如果不是，则检查一下他们是否都是1即可。

代码如下

 1 class Solution {
 2 public:
 3     long long rangeBitwiseAnd(long long m, long long n) {
 4         long long ans=0;
 5         long long num=1;
 6         long long x,y;
 7         for(int i=0;i<32;i++)
 8         {
 9             num<<=1;
10             if((n-m)<=num/2)
11             {
12                x=n%num;
13                y=m%num;
14                if(x<=num/2-1)
15                  x=0;
16                  else
17                  x=1;
18                 if(y<=num/2-1)
19                  y=0;
20                  else
21                  y=1;
22                  if(x&&y)
23                  ans+=1<<i;
24             }
25             
26         }
27         return ans;
28     }
29 };