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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Bitwise AND of Numbers Range

Difficulty: Medium

Problem Description

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Key Insights

  • The bitwise AND operation results in a number that has a 1 in each bit position where all operands have a 1.
  • If the range includes numbers that differ in higher bit positions, those bits will result in 0 in the final AND.
  • The result is determined by finding the common prefix of the binary representations of left and right.

Space and Time Complexity

Time Complexity: O(log(max(left, right)))
Space Complexity: O(1)

Solution

To solve the problem, we can use the following approach:

  1. Identify the common prefix of the binary representations of left and right.
  2. Shift both left and right until they become equal, counting the number of shifts.
  3. The result is the common prefix shifted back to its original position.

This algorithm is efficient due to its logarithmic time complexity, as it only involves bit shifts.

Code Solutions

def rangeBitwiseAnd(left: int, right: int) -> int:
    shift = 0
    while left < right:
        left >>= 1
        right >>= 1
        shift += 1
    return left << shift
← Back to All Questions