201. Bitwise AND of Numbers Range #

Problem #

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

Problem Summary #

Given a range [m, n], where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range (including both endpoints m and n).

Solution Ideas #

• This problem requires outputting the result after performing the AND operation on all numbers in the interval [m,n].

• For example, suppose the interval is [26,30]. The numbers in this interval represented in binary are:

  11010
  11011
  11100
  11101
  11110

• It can be observed that when all these numbers are ANDed together, as long as there is a 0 in a bit position, the final result for that bit is 0, so we need to find from right to left the bit position from which the bits are not 0. Continuously right-shift the left boundary and the right boundary, shifting away the 0s on the right until the two become equal; then we have found the position from which the bits start to all be nonzero. Record how many bits were shifted during the right-shifting process, and finally append 0s to the right of m or n. In the example above, 11000 is the final result.

• There is also a second solution for this problem, still using the interval [26,30] as an example. The last 3 bits of the numbers in this interval keep changing between 0 and 1. So if we clear all the trailing 1s, we get the final required result. When n == m or n < m, exit the loop, which means all the differing lower bits have already been flattened, and all 1s have been cleared to 0. Therefore, the key operation is n &= (n - 1), which clears the lowest set bit. This algorithm is called the Brian Kernighan algorithm.

Code #

package leetcode

// Solution 1
func rangeBitwiseAnd1(m int, n int) int {
	if m == 0 {
		return 0
	}
	moved := 0
	for m != n {
		m >>= 1
		n >>= 1
		moved++
	}
	return m << uint32(moved)
}

// Solution 2 Brian Kernighan's algorithm
func rangeBitwiseAnd(m int, n int) int {
	for n > m {
		n &= (n - 1) // Clear the lowest set bit
	}
	return n
}