Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
solve.c

README.md

Bitwise AND of Numbers 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

直接暴力求解。因为n & n -1就是把把n的最后一个1清空,并且只要其中有一个为0,&操作就为0,于是我们从后面开始计算,遇到2^n & 2^n - 1必然会提前退出

Code

int slowRangeBitwiseAnd(int m, int n) {
	int ans = n;
	for (int i = n - 1; i >= m && ans; --i)
		ans &= i;
	return ans;
}

Solution 2

结合上次的思路,2^n & 2^n - 1等于0,设N为n的最高位为1的数,比如n = 7, N = 4, n = 8, N = 8, n = 11, N = 8, 则若m < N, 直接返回0

Code

int midRangeBitwiseAnd(int m, int n)
{
	int base = 1;
	int t = n;
	while ((t >> 1)) {
		base <<= 1;
		t >>= 1;
	}
	if (m < base)
		return 0;
	int ans = n;
	for (int i = n - 1; i >= m; --i)
		ans &= i;
	return ans;
}

上面解法只是过滤了当值等于0的情况,而结果不等于0时,并不能减少计算量

Solution 3

我们取m,n二进制的公共前缀,后面添加0直到与n等长,比如n = 101011, m = 101000, 则为101000,后面部分为00~11,相与必然为0, 因此101000就是最后的结果

因此此题转化成求n,m的二进制公共前缀.

Code

int rangeBitwiseAnd(int m, int n) {
	if (m == n)
		return m;
	if (m == 0)
		return 0;
	int base = 1;
	int t = n;
	while ((t >> 1)) {
		base <<= 1;
		t >>= 1;
	}
	int ans = 0;
	while (base) {
		int a = base & m;
		int b = base & n;
		if (a != b)
			return ans;
		ans |= a;
		base >>= 1;
	}
	return ans;
}

循环至多32次,大大减少了计算量

You can’t perform that action at this time.