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.
201. Bitwise AND of Numbers Range.go
201. Bitwise AND of Numbers Range_test.go
README.md

README.md

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

Example 1:

Input: [5,7]
Output: 4

Example 2:

Input: [0,1]
Output: 0

题目大意

给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。

解题思路

  • 这一题要求输出 [m,n] 区间内所有数的 AND 与操作之后的结果。

  • 举个例子,假设区间是 [26,30],那么这个区间内的数用二进制表示出来为:

    11010
    11011
    11100
    11101
    11110

  • 可以观察到,把这些数都 AND 起来,只要有 0 的位,最终结果都是 0,所以需要从右往前找到某一位上不为 0 的。不断的右移左边界和右边界,把右边的 0 都移走,直到它们俩相等,就找到了某一位上开始都不为 0 的了。在右移的过程中记录下右移了多少位,最后把 m 或者 n 的右边添上 0 即可。按照上面这个例子来看,11000 是最终的结果。

  • 这一题还有解法二,还是以 [26,30] 这个区间为例。这个区间内的数末尾 3 位不断的 0,1 变化着。那么如果把末尾的 1 都打掉,就是最终要求的结果了。当 n == m 或者 n < m 的时候就退出循环,说明后面不同的位数已经都被抹平了,1 都被打掉为 0 了。所以关键的操作为 n &= (n - 1) ,清除最低位的 1 。这个算法名叫 Brian Kernighan 算法。

You can’t perform that action at this time.