Bitwise AND of Numbers Range--LeetCode

àì夳堔傛蜴生んèń 2022-08-07 16:56 36阅读 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.

思路：第一个思路肯定是从第一个数开始按位与，但是这样的复杂度太高，开始有新的改进，如果这个范围内有2的幂，那么从这个开始按位或即可，这个2的幂要紧挨着n，如果发现这个2的幂次小于m,那么仍然从这个范围开始安装或。

int rangeBitwiseAnd(int m, int n) 
    {
    	int i;
    	int result ;
    	for(i=0;;i++)
    	if(pow(2,i)>n)
    		break;
    	if(pow(2,i-1) < m)
    	{
    		result = m;
    		for(i=m+1;i<=n;i++)
    		 result  &= i; 
    	}   
    	else
    	{
    		result = pow(2,i-1);
    		i = pow(2,i-1)+1;
    		for(;i<=n;i++)
    		 result &= i;
    	}     
    	return result;
    }

看别人的代码，发现有更快的，对于一个连续的数字序列，两个相邻的两个数最后一位肯定是不一样的，那么只要m!=n,那么最后一位肯定是0，那么我们就看从哪一位开始m==n即可。

int rangeBitwiseAnd(int m, int n) {  
            int offset = 0;  
            while (m && n)  
            {  
                if (m == n)  
                {  
                    return m << offset;  
                }  
                m >>= 1;  
                n >>= 1;  
                offset++;  
            }  
      
            return 0;  
        }

ps:其实我们也应该很容易理解这个问题，最后的与肯定是从某一位开始都相同，那么我们只需要看最大和最小的两个数，从哪一位开始是相同的，也就是看最大和最小的两个值的高几位相同。 当然我们也可以使用从高位往地位判断，有多少位是相同的。