leecode 解题总结：201. Bitwise AND of Numbers Range

#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*问题: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.分析:bitwise:按位。题目将给定范围内的数据全部进行与操作，返回结果。	5:0101	6:0110	7:0111AND:  0100得到4.由于与操作中只要某一位上有1个为0，那一位必定为0，暴力破解就是先遍历32位，然后对每一位上遍历每个数，进行AND，总的时间复杂度为O(32n).如果进行优化，就是一旦这一位上出现了0，后续无需遍历其他数在该位上的值2147483646:11111111...102147483647:11111111...11输入:5 70 31 21474836472147483646 21474836472147483647 2147483647输出:40021474836462147483647报错：Input:2147483646 2147483647Output:0，Expected:2147483646被坑了，2147483647之后累加会变成-1，导致一直存在问题，这里需要判断如果为2147483647判断完了，直接break超时了:当输入的两个数一样的时候，例如：2147483647，应该直接返回这个数本身关键:1 参见解法:http://www.jianshu.com/p/ea0f6aa14ef4寻求[m,n]中And之后的结果，本质上m到n中高位bit是不变的，低位bit变化一直连续的而m和n的共同高位bit是最少的，只需计算m和n的非共同高位bit个数num。然后将已经相等的m和n中的m向左移动num位即可*/class Solution {public:    int rangeBitwiseAnd(int m, int n) {		//两个数相同，直接返回结果		int countBit = 0;		while(m != n)		{			m >>= 1;//m向左移动			n >>= 1;			countBit++;		}		//m向左移动即可		return (m << countBit);    }};void PRint(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 Solution solution;	 int m;	 int n;	 while(cin >> m >> n )	 {		 int answer = solution.rangeBitwiseAnd(m , n);		 cout << answer << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}/*    int rangeBitwiseAnd(int m, int n) {		//两个数相同，直接返回结果		if(m == n)		{			return m;		}		//遍历每一位		int value = 1;		int result = 0;		bool isZero = false;        for(int i = 0 ; i < 32 ; i++)		{			value = (1 << i);			isZero = false;			for(int j = m ; j <= n ; j++)			{				if(0 == (value & j))				{					isZero = true;					break;				}				//如果j已经变成最大值，加1后会变成-1，造成错误，这里直接退出				if(INT_MAX == j)				{					break;				}			}			//只有该位为1，才需要处理			if(!isZero)			{				result |= (value);			}		}		return result;    }*/