Frontend School

Range Bitwise AND

DSA
medium

Range Bitwise AND

Medium
Bit Manipulation
Mathematics

Overview

Imagine you're developing a system for managing unique identifiers or data blocks, where common bit patterns across a range of IDs can signify shared properties or optimize data processing. For instance, in a distributed file system, files within a certain ID range might share a common prefix in their internal metadata, which could be leveraged for faster lookups or integrity checks.

This problem challenges you to efficiently find the bitwise AND of all numbers within a given inclusive range [m, n]. This operation helps in identifying the common leading bits among all numbers in that range, which can be crucial for various optimization and classification tasks.

What you need to do / Task

Implement a function rangeBitwiseAnd that computes the bitwise AND of all numbers in a given inclusive range [m, n].

Input & output

  • m: An integer representing the start of the inclusive range [m, n]. (0 <= m <= n)
  • n: An integer representing the end of the inclusive range [m, n].
  • Returns: An integer, which is the bitwise AND of all numbers from m to n (inclusive).

Clarifications

  • What if m and n are the same? If m == n, the range contains only one number, so the result is m itself.
  • What about the size of m and n? They will fit within standard 32-bit signed integer limits, meaning their bitwise operations behave as expected in most languages (e.g., JavaScript's bitwise operators treat numbers as 32-bit signed integers).

Examples

1

Example 1

Input:

m = 5, n = 7

Output:

4

Note:

Binary representations: 5 is 0101, 6 is 0110, 7 is 0111. The bitwise AND of these three numbers is 0100, which is 4.

2

Example 2

Input:

m = 0, n = 0

Output:

0

Note:

The range contains only 0. 0 & 0 = 0.

3

Example 3

Input:

m = 1, n = 2147483647

Output:

0

Note:

The range includes numbers like 1 (binary ...01) and 2 (binary ...10). Since these two numbers already result in 1 & 2 = 0, the bitwise AND of the entire range will also be 0.

Constraints

Constraints & assumptions

  • 0 <= m <= n <= 2^31 - 1
  • The solution should be efficient, avoiding iterating through all numbers in the range if n - m is very large.

Out of scope

  • Handling non-integer inputs or inputs outside the specified range [0, 2^31 - 1].
  • Arbitrary precision arithmetic; standard integer types are sufficient.

What interviewers evaluate

  • Correctness of the bit manipulation logic and understanding of bitwise AND properties.
  • Efficiency of the algorithm, particularly for wide ranges.
  • Ability to handle edge cases, such as m = 0 or m = n.
  • Clarity, readability, and maintainability of the code.

Loading editor...