[LeetCode] 201. Bitwise AND of Numbers Range

轉自LeetCode

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.

<Solution>
因為是 LeetCode，當然不可能直接歷遍去 and 每個數，想法如下

• 因為要找到相同的 bits，所以只要當 m != n，把 m 和 n 都往右移一個 bit，直到相等

• 在上面的 loop 中，也要記錄右移了幾個位元，因為最後必須將相同步分左移移回它們原本的位置

code 如下(參考資料)
c++

	class Solution {
	public:
	int rangeBitwiseAnd(int m, int n) {
	int cnt = 0;
	while(m != n) {
	m >>= 1;
	n >>= 1;
	++cnt;
	}
	return (m << cnt)
	}
	};

view raw bitwiseAndOfNumbersRange.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun rangeBitwiseAnd(left: Int, right: Int): Int {
	var cnt = 0
	var leftNum = left
	var rightNum = right
	while(leftNum != rightNum) {
	leftNum = leftNum shr 1
	rightNum = rightNum shr 1
	++cnt
	}
	return leftNum shl cnt
	}
	}

view raw bitwise_AND_of_numbers_range.kt hosted with ❤ by GitHub