We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Bitwise AND of Numbers Range

Number: 201

Difficulty: Medium

Paid? No

Companies: Amazon, Yahoo, Google

Problem Description

Given two integers left and right that represent a range [left, right], compute the bitwise AND of all numbers in the range. The result should include only those bits that remain 1 across every number within the range.

Key Insights

  • The bitwise AND operation only retains a bit if that bit is 1 in every number in the given range.
  • The key observation is that the range of numbers will eventually force a bit position to flip from 1 to 0; hence, only the common prefix (the leftmost bits that do not change when moving from left to right) contributes to the final result.
  • The solution involves shifting both left and right until they match, tracking the number of shifts, and then shifting back to obtain the common bits.

Space and Time Complexity

Time Complexity: O(log n), where n is the number represented by right, since we process a fixed number of bits (typically 32 bits for 32-bit integers). Space Complexity: O(1), since only a few integer variables are used.

Solution

The main idea is to discard the differing bits between left and right. We do this by shifting both numbers to the right until they become equal, which effectively removes the non-common bits at the right. The number of shifts performed tells us how many trailing zeros must be added back by shifting left. This approach efficiently finds the common prefix shared by both numbers, which represents the bitwise AND of all numbers in the given range.

Data Structures Used:

  • Only integer variables are used.

Algorithmic Approach:

  1. While left is not equal to right, right-shift both left and right (i.e., remove the least significant bit).
  2. Count the number of shifts performed.
  3. Once left equals right, shift back to the left by the counted amount to restore the common prefix in its original bit positions.
  4. The final number is the bitwise AND of all numbers in the range.

Code Solutions

# Function to calculate bitwise AND of numbers in range [left, right]
def rangeBitwiseAnd(left: int, right: int) -> int:
    shift = 0  # Counter for number of shifts performed
    # Shift both numbers right until they are equal
    while left != right:
        left >>= 1  # Right shift left by 1
        right >>= 1  # Right shift right by 1
        shift += 1  # Increment shift counter
    # Shift left to restore the common prefix in its original position
    return left << shift  # Left shift by the number of shifts

# Example usage
print(rangeBitwiseAnd(5, 7))  # Expected output: 4
← Back to All Questions