NUHMAN.com

Problem Statement

Given two integers m and n, where m <= n, return the bitwise AND of all numbers in the range from m to n (inclusive).

Function Signature:

go

func rangeBitwiseAnd(m int, n int) int

Example 1:

go

m, n := 5, 7
fmt.Println(rangeBitwiseAnd(m, n)) // Output: 4

Example 2:

go

m, n := 0, 1
fmt.Println(rangeBitwiseAnd(m, n)) // Output: 0

Constraints:

• 0 <= m <= n <= 2147483647

Approach

To solve the problem, we need to compute the bitwise AND of all numbers from m to n. We could try iterating through all the numbers in the range and performing a bitwise AND on each, but this approach would be inefficient, especially when n - m is large.

Instead, we can take advantage of the following key observation:

• As we move from m to n, the result of the bitwise AND will "shrink" and lose the bits that differ between m and n. This happens because as numbers increase, their binary representation shifts and more bits start to differ.

Key Insight:

The bitwise AND of all numbers in a range [m, n] will be the common prefix of m and n until the binary representation of m and n starts to differ. Therefore, we can keep shifting both m and n to the right (dividing by 2) until m equals n. The result of the AND operation will then be the common prefix left-shifted back to its original position.

Steps:

1. Shift until m == n: While m is not equal to n, keep right-shifting both m and n by one bit. This effectively removes the bits that will differ in the range.
2. Left shift the result: Once m and n are the same, left-shift m (or n) back to the original position to restore the common prefix.

Time Complexity:

The time complexity is O(log n) because we are only performing right shifts, and the number of shifts required is proportional to the number of bits in n.

Go Implementation

go

package main

import "fmt"

// Function to compute the bitwise AND of numbers in the range [m, n]
func rangeBitwiseAnd(m int, n int) int {
    shiftCount := 0
    
    // Keep shifting until m == n
    for m < n {
        m >>= 1
        n >>= 1
        shiftCount++
    }

    // Left shift m back to restore the common prefix
    return m << shiftCount
}

func main() {
    // Example 1
    m1, n1 := 5, 7
    fmt.Println(rangeBitwiseAnd(m1, n1)) // Output: 4

    // Example 2
    m2, n2 := 0, 1
    fmt.Println(rangeBitwiseAnd(m2, n2)) // Output: 0
}

Explanation of the Code:

1. rangeBitwiseAnd Function:

• Input: Takes two integers m and n representing the range.
• Loop: We continue right-shifting both m and n while they are not equal. Each shift removes the least significant bit that differs between m and n.
• Shift Count: We count the number of shifts required to make m equal to n. This will be used to restore the common prefix later.
• Return Value: After m and n are equal, we left-shift m by shiftCount to get the common prefix.

2. Main Function:

• Creates two example cases (m1, n1 and m2, n2).
• Calls rangeBitwiseAnd to calculate and print the result for each case.

Example Walkthrough

Example 1:

Input:

go

m, n := 5, 7

The binary representations of 5 and 7 are:

• 5 = 101
• 7 = 111

1. First, shift both 5 and 7 right by one bit:

• 5 = 101 → 10 (Shifted)
• 7 = 111 → 11 (Shifted)
• m = 2, n = 3 now.

1. Shift both 2 and 3 right by one bit:

• 2 = 10 → 1 (Shifted)
• 3 = 11 → 1 (Shifted)
• m = 1, n = 1 now, so we exit the loop.

1. Since m == n, we left-shift m (which is 1) by 2 positions (the number of shifts):

• 1 << 2 = 100, which is 4.

Output: 4

Example 2:

Input:

go

m, n := 0, 1

The binary representations of 0 and 1 are:

• 0 = 0
• 1 = 1

1. First, shift both 0 and 1 right by one bit:

• 0 = 0 → 0 (Shifted)
• 1 = 1 → 0 (Shifted)
• m = 0, n = 0 now, so we exit the loop.

1. Since m == n, we left-shift m (which is 0) by 1 position:

• 0 << 1 = 0.

Output: 0

Conclusion

The LeetCode 201: Bitwise AND of Numbers in Range problem can be solved efficiently using bitwise operations by exploiting the common prefix of m and n. The solution runs in O(log n) time complexity, which is optimal for this problem. The approach efficiently handles large numbers by avoiding brute-force iteration.