Bitwise AND of Numbers Range

Medium
414.

Bitwise AND of Numbers Range

Bitwise AND of Numbers Range is a medium coding problem on bit manipulation, asked in Amazon, Google and Microsoft interviews.

Given two integers left and right with left <= right, return the bitwise AND of every number in the inclusive range [left, right].

Example 1

Input
left = 5, right = 7
Output
4

Example 2

Input
left = 0, right = 0
Output
0

Example 3

Input
left = 1, right = 2147483647
Output
0

Constraints

  • 0 <= left <= right <= 2147483647
  • The answer fits in a signed 32-bit integer.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var rangeBitwiseAnd = function(left, right) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Bitwise AND of Numbers Range — Problem & Solution

Bitwise AND of Numbers Range solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Bitwise AND of Numbers Range is a medium coding problem on bit manipulation, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Bit Manipulation
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given two integers left and right with left <= right, return the bitwise AND of every number in the inclusive range [left, right].

Example 1

Input: left = 5, right = 7
Output: 4

Example 2

Input: left = 0, right = 0
Output: 0

Example 3

Input: left = 1, right = 2147483647
Output: 0

Constraints

  • 0 <= left <= right <= 2147483647
  • The answer fits in a signed 32-bit integer.

Hints for Bitwise AND of Numbers Range

  1. Hint 1

    Any bit that changes anywhere in the range gets ANDed with a 0 somewhere, so it ends up 0.

  2. Hint 2

    Only the common binary prefix of left and right survives.

  3. Hint 3

    Shift both right until they match, then shift the result back by the same amount.

How to solve Bitwise AND of Numbers Range

Any bit that changes anywhere in the range is ANDed with a 0, so only the common binary prefix of left and right survives.

Approach

  1. Shift both right until they are equal, counting shifts.
  2. Shift the common value back left by that count.

Why it works

If left and right differ at bit b, then somewhere in between bit b flips and every lower bit cycles through 0, so all bits from b down are cleared; the prefix above b is shared by every number in the range.

Complexity

  • Time — O(log right)
  • Space — O(1)

Pitfalls

  • Iterating the range is far too slow when right - left is large.

Reference solution

Python

def rangeBitwiseAnd(left: int, right: int) -> int:
    shift = 0
    while left != right:
        left >>= 1
        right >>= 1
        shift += 1
    return left << shift

Java

public static int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    int a = left, b = right;
    while (a != b) {
        a >>>= 1;
        b >>>= 1;
        shift++;
    }
    return a << shift;
}

C++

int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    unsigned int a = (unsigned int) left, b = (unsigned int) right;
    while (a != b) {
        a >>= 1;
        b >>= 1;
        shift++;
    }
    return (int) (a << shift);
}

JavaScript

var rangeBitwiseAnd = function(left, right) {
    let shift = 0;
    let a = left, b = right;
    while (a !== b) {
        a = Math.floor(a / 2);
        b = Math.floor(b / 2);
        shift++;
    }
    return a * Math.pow(2, shift);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 146 bit manipulation problems · the whole catalogue

Learn the technique: Bit Manipulation