201. Bitwise AND of Numbers Range

  • 33.3%

https://leetcode.com/problems/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.

1
For example, given the range [5, 7], you should return 4.

方法一:

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int cnt = 0;
while(m!=n){
m >>= 1;
n >>= 1;
cnt++;
}
return m<<cnt;
}
};

9ms, 44.28%, October 15, 2016

https://discuss.leetcode.com/topic/12133/bit-operation-solution-java

Bit operation solution(JAVA)

The idea is very simple:

  1. last bit of (odd number & even number) is 0.
  2. when m != n, There is at least an odd number and an even number, so the last bit position result is 0.
  3. Move m and n rigth a position.

Keep doing step 1,2,3 until m equal to n, use a factor to record the iteration time.

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int rangeBitwiseAnd(int m, int n) {
if(m==0)
return 0;
int moveFactor = 1;
while(m!=n){
m >>= 1;
n >>= 1;
moveFactor <<= 1;
}
return m * moveFactor;
}
}

cpp


32ms, 64.35%, October 15, 2016

https://discuss.leetcode.com/topic/13508/one-line-c-solution

One line C++ solution

Consider the bits from low to high. if n > m, the lowest bit will be 0, and then we could transfer the problem to sub-problem: rangeBitwiseAnd(m>>1, n>>1).

1
2
3
4
5
6
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
return (n>m) ? (rangeBitwiseAnd(m/2, n/2)<<1) : m;
}
};

https://discuss.leetcode.com/topic/17491/fast-three-line-c-solution-and-explanation-with-no-loops-or-recursion-and-one-extra-variable

Fast three line C++ solution and explanation with no loops or recursion and one extra variable

Whenever a bit changes when counting from m to n, that bit will be 0 in the AND of the range. So we consider the XOR x of m and n. The leftmost 1 bit in x is the last bit that changes at some point when counting from m to n. This bit and the bits to the right of it are all 0 in the AND of the range. We can easily fill all the bits to the right of that bit with 1s using the OR operations below to create a mask. This technique “smears” the 1 bits in x to the right. Then it’s just a matter of returning the rest of m excluding those bits (the bits in m that did not change when counting up to n), which is precisely the AND of the range from m to n.

1
2
3
4
5
6
7
8
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
unsigned int x = m ^ n;
x |= x >> 1, x |= x >> 2, x |= x >> 4, x |= x >> 8, x |= x >> 16;
return m & ~x;
}
};

my code:

注意最后一行 n<< i, 不能为1<< i; 考虑m n都为0的情况。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int i = 0;
while(m!=n){
m>>=1;
n>>=1;
i++;
}
return n<<i;
}
};

python


122ms, 75.44%, October 15, 2016

https://discuss.leetcode.com/topic/28538/java-python-easy-solution-with-explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def rangeBitwiseAnd(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
i = 0
while m != n:
m >>= 1
n >>= 1
i += 1
return n << i
谢谢你,可爱的朋友。