LeetCode 201. Bitwise AND of Numbers Range

201. Bitwise AND of Numbers Range

Description Submission Solutions

Total Accepted: 50473
Total Submissions: 151430
Difficulty: Medium
Contributors: Admin

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.

Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.

Subscribe to see which companies asked this question.

【题目分析】

给定一个整数范围，范围在此范围内的所有数字进行与操作的结果。

【思路】

1. 直接循环的话最多需要进行2147483647次与操作，这会导致超时。

2. 通过观察数字的规律来找到更可行的方法。

在这个范围内的数字的二进制串上，如果有一个位置有0，那么结果中这个位置必然为0. 观察下面规律：

[5, 7]里共有三个数字(5,6,7)，二进制分别为：

1 01　　1 10　　1 11

相与后的结果为100

[9, 11]里共有三个数字(9,10,11)，二进制分别为：

1 001　　1 010　　1 011

相与后的结果为1000

[26, 30]里共有五个数字(26,27,28,29,30)，二进制分别为：

11 010　　11 011　　11 100　　11 101　　11 110

相与后的结果为11000

仔细观察我们可以得出，我们要求出的结果就是给定范围内所有数的左边公共1的部分，其他位都为0。

【java代码】

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

【总结1】

1. 题目看似简单，但是要解决的话需要很多技巧。

2. 需要对二进制数有深刻的理解，对数据的位操作要熟练起来。