0201. Bitwise AND of Numbers Range (Medium)

Question

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1

1
2

Input: [5,7]
Output: 4

Example 2

1
2

Input: [0,1]
Output: 0

分析/解題

給定一個範圍m, n，且0≤m≤n≤2147483647(也就是2³¹-1)，
回傳這個範圍內(inclusive，即含n)的所有數字的bitwise AND的結果。

首先這題要先理解inclusive表示頭跟尾都要 ，
例如[5, 7]，其範圍內的所有數字就是5, 6, 7。
再者如前面提到過的bitwise operation的部份，
這邊做的是對每個bit一一對應做AND的操作。

我們先來看一下範例1，將其化成二進位：

1
2
3
4

5   : 101
6   : 110
7   : 111
AND : 100 => Output: 4

注意到由於AND操作要求兩個bit都是1結果才是1 ，
所以中間一旦出現任意一個0的話，當個bit的AND結果最終必然是0 。
由於

已經知道m≤n了，假設m跟n前面存在一組位元長得一模一樣，
例如：

1
2

m: 100100101000 (2344)
n: 100100111111 (2367)

可以明顯看出從m到n的部份，1001001 的位元是完全不變的，
AND出來這部分顯然也會保留 ，因為每個數字的這部份都一樣。

那麼後面呢？
由於m ≤ n，
所以在後面不相同的狀況下，開始不相同的m的第一個bit顯然會是0 ，
n的第一個bit顯然會是1 ，那麼從m一路到n的bit變化，
就必然有從011…1到100…0 的情況，
所以後面的所有bit皆至少有出現過一次0 ，
這會使得後面的區塊經過AND完以後肯定是0 。

所以整個問題就可以化簡成：
找到m和n的最前面相同的bit，再將後面補上0即為答案 。

要找這個很簡單，每次檢查m, n是否相等，若否，
則各自向右移動一個bit，最終到** m, n相等時，
只要乘上對應的位移倍數，即為解答。
讀者可以自行選用將factor視為位移位數** 或必須相乘的倍數 ，
兩者速度基本相似。

除此之外還有另一個思路，既然我們只是想要n的前面那區bits，
那就一次從n剝離一個bit
( n &= n-1 , 先前的題目有提到可以用來一次去除最低位的bit)，
直到n≤m為止。這時候留下來的n即為答案，因為低位的全被剝離了。

依此，寫成程式碼。
(三者速度差異不大，但最後一種看起來最簡單，讀者可以自行斟酌選擇)

Java

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(n的長度)/O(1)，
因為要做到哪一步端看什麼時候找到m和n前面相同的位置)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~