LeetCode Bitwise AND of Numbers Range

LeetCode 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.


求把从m~n的所有整数相与的结果。

暴力方法就是从m到n遍历一遍,把所有数都相与一下。但是TLE。

这题明显是个数学题或者找规律题。网上的解法大多数是这样的,把m~n的所有数相与的结果等于m和n这两个数的二进制的最长公共前缀。比如题目中的[5,7],5和7的二进制分别为101和111,最长公共前缀就是100=4,后两位不一样也要补0。再比如[26,30],26和30的二进制分别为11010和11110,最长公共前缀为11000=24。

知道这个规律就好办了,因为m和n都是正数,不断同时把m和n往右移,直到他们相等,最后再把m往左移回去就是最终结果。代码如下:

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

本代码提交AC,用时69MS。

Leave a Reply

Your email address will not be published. Required fields are marked *