Frontend School

Range Bitwise AND

DSA
medium

Range Bitwise AND

Medium
Bit Manipulation
Mathematics

Overview

In performance-critical applications, especially within automotive systems or embedded software at Tesla, understanding and manipulating data at the bit level is essential for efficiency and resource optimization. Imagine a scenario where you need to determine common properties across a sequence of identifiers or sensor readings, represented as integers. The bitwise AND operation can efficiently reveal these shared characteristics.

This problem challenges your ability to leverage bitwise operations for efficient computation, a critical skill for performance-sensitive applications in areas like firmware, low-level drivers, or high-throughput data processing.

What you need to do / Task

Implement a function rangeBitwiseAnd that takes two non-negative integers, m and n, representing an inclusive range [m, n]. The function should return the bitwise AND of all numbers in this range, inclusive.

Your solution must be efficient and avoid iterating through all numbers in the range, especially for large ranges, as this would be too slow.

Input & output

function rangeBitwiseAnd(m: number, n: number): number;
  • m: An integer, the lower bound of the range.
  • n: An integer, the upper bound of the range.
  • Returns: An integer, the bitwise AND of all numbers from m to n (inclusive).

Clarifications

  • Large Ranges: Your solution needs to be efficient enough to handle cases where n - m is very large, without timing out.
  • m == n: If m and n are equal, the function should simply return m (or n).

Examples

1

Example 1

Input:

m = 5, n = 7

Output:

4

Note:

Binary representations: 5 (0101), 6 (0110), 7 (0111). Their bitwise AND is 0100, which is 4. The common prefix of 5, 6, and 7 is '010'.

2

Example 2

Input:

m = 0, n = 0

Output:

0

Note:

The range only contains the number 0. The bitwise AND of 0 is 0.

3

Example 3

Input:

m = 1, n = 2147483647

Output:

0

Note:

This is a very wide range. Since the range includes numbers like 1 (0...01), 2 (0...10), 3 (0...11), etc., eventually all bit positions will have a 0 in at least one number within the range, except for the common leading zeros. Thus, the final bitwise AND will be 0.

4

Example 4

Input:

m = 6, n = 7

Output:

6

Note:

Binary representations: 6 (0110), 7 (0111). Their bitwise AND is 0110, which is 6. The common prefix of 6 and 7 is '011'.

Constraints

Constraints & assumptions

  • 0 <= m <= n <= 2^31 - 1
  • The numbers m and n are non-negative.
  • Assume valid input where m <= n.

Out of scope

  • Handling negative input numbers.
  • Input validation for m <= n.

What interviewers evaluate

  • Correctness: The solution correctly computes the bitwise AND for all valid ranges, including edge cases.
  • Efficiency: The algorithm avoids a linear scan through the range, demonstrating an understanding of bitwise optimization.
  • Clarity: The code is well-structured, readable, and the logic is easy to follow.
  • Problem-Solving: The candidate articulates the core insight behind the bit manipulation strategy.

Loading editor...