LeetCode Q201: Bitwise AND of Numbers of Range

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.

Solution 1:

Need to tell whether each bit contains a zero? Basically, if m - n > 2^i, where i represents for i-th bit. then i-th bit must be zero in result.

	int rangeBitwiseAnd(int m, int n) {
	if(m==n)
	return m;
	int diff=n-m;
	int base;
	while(true){
	int tmp=(diff-1)&diff;
	if(tmp!=0)
	diff=(diff-1)&diff;
	else
	break;
	}
	diff=diff<<1;
	base=diff-1;
	int mask=~base;
	int res=(m&n)&mask;
	return res;
	}

view raw Q201BitwiseANDofNumbersRange.cpp hosted with ❤ by GitHub

Solution 2:
Consider the bits from low to high. if n>m, the lowest bit will be 0, then we could transfer the problem to sub-problem.

	class Solution {
	public:
	int rangeBitwiseAnd(int m, int n) {
	int trans = 0;
	while(m != n)
	{
	++ trans;
	m >>= 1;
	n >>= 1;
	}
	return m << trans;
	}
	};

view raw Q201-1.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int rangeBitwiseAnd(int m, int n) {
	int first1Pos = 0;
	int t = m^n;
	for(int i=0; i<32; i++)
	first1Pos= ((t>>i)&1)==1? i:first1Pos;
	int res = m&n;
	int zero=0;
	for(int i=first1Pos; i>=0; i--){
	if(((res>>i)&1)==0||zero==1){
	res = res & (~(1<<i));
	zero=1;
	}
	}
	return res;
	}
	};

view raw Q201Rnd2.cpp hosted with ❤ by GitHub

Rnd3 sol:

	class Solution {
	public:
	int rangeBitwiseAnd(int m, int n) {
	int res = m&n;
	int diff = log2(n-m);
	int tmp = 1;
	for(int i=0; i<=diff; i++)
	res = res&((~tmp)<<i);
	return res;
	}
	};

view raw Q201Rnd3.cpp hosted with ❤ by GitHub