未分類

Bitwise AND of Numbers Range

BitManipulation, Go, 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.

提示 解題應用
BitManipulation AND

Default:

1
2
3
func rangeBitwiseAnd(m int, n int) int {
}

解答思路:

仔細觀查一數序做AND的話會發現存在一種規律，從範圍中最後一個數字往前做AND的時候，每往前做一次AND其二進位值最右側的1就會歸0，例如範圍[4, 7]:

7先與6做AND，7從111變為110最右側的1歸0

1
2
3
7 111
6 110
& 110

再繼續與5做AND，110變為100最右側的1歸0

1
2
3
7&6 110
5   101
&   100

最後到範圍的第一個數字時，到目前為止的值剛好就與4相同，因此沒辦法將最右側的1歸0，但此時的值就會是我們要的結果

1
2
3
7&6&5 100
4     100
&     100

因此只要以範圍最後一個值為主不斷的將最右側的1歸0，直到該值小於等於範圍第一個值為止，意思就等同是整個範圍都做AND的結果。

程式碼解說:

既然知道要以範圍的最後一個值為主不斷的將最右側的1歸0，其做法就只是將”該數”與”該數-1”做&(AND)即可，這個技巧也可以用來判斷二進位有多少個1或判斷是否為2的n次方，最後就只是不斷重覆上述動作直到該值小於等於範圍的第一個值為止，此時剩餘的值就等同是整個範圍都做AND的結果

1
2
3
4
for m < n {
	n = n & (n - 1)
}
return n

完整程式碼:

1
2
3
4
5
6
func rangeBitwiseAnd(m int, n int) int {
	for m < n {
		n = n & (n - 1)
	}
	return n
}

總結:

給一數序要將其範圍內的所有值做&(AND)並回傳結果，只要以範圍最後一個值為主不斷的將二進位表示的最右側1歸0，直到該值小於等於範圍第一個值為止，意思就等同是整個範圍都做AND的結果，至於每次要如何將該數二進位的最右側1歸0只要將”該數”與”該數-1”做&(AND)即可。

分享到