Bitwise AND of Numbers Range - Practice Coding Problems

Bitwise AND of Numbers Range - Problem

Bit Manipulation Medium

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

The bitwise AND operation compares each bit position of the numbers and returns 1 only when all corresponding bits are 1, otherwise returns 0.

Example: For range [5, 7], we compute 5 & 6 & 7 = 4

Input & Output

Example 1 — Basic Range

$ Input: left = 5, right = 7

› Output: 4

💡 Note: Binary: 5 (101) & 6 (110) & 7 (111) = 100 = 4. Only the leftmost bit stays 1 across all numbers.

Example 2 — Same Number

$ Input: left = 0, right = 0

› Output: 0

💡 Note: When left equals right, the AND of a single number is the number itself: 0.

Example 3 — Large Range

$ Input: left = 1, right = 2147483647

› Output: 0

💡 Note: Large range spans multiple bit positions, so all bits get zeroed out through the AND operations.

Constraints

0 ≤ left ≤ right ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input Range

Given left=5, right=7, find AND of all numbers

Binary Analysis

Compare binary representations to find common bits

AND Result

Only common prefix bits survive

Key Takeaway

🎯 Key Insight: Only the common binary prefix survives the AND operation across any range

Asked in

G Google 15 M Microsoft 12 A Amazon 8

The key insight is that bitwise AND eliminates all differing bits across the range. The optimal approach finds the common binary prefix of the range boundaries. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Common Prefix Method	O(log n)	O(1)	Find the longest common binary prefix of left and right
Brute Force Iteration	O(n)	O(1)	AND all numbers from left to right one by one

Common Prefix Method — Algorithm Steps

Compare left and right bit by bit
Find the longest common prefix
Right-shift both numbers until they become equal
Left-shift back to get the result

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial

Compare binary representations

Shift Right

Remove differing bits from right

Shift Back

Restore common prefix

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int left, int right) {
    int shift = 0;
    while (left != right) {
        left >>= 1;
        right >>= 1;
        shift++;
    }
    return left << shift;
}

int main() {
    int left, right;
    scanf("%d", &left);
    scanf("%d", &right);
    int result = solution(left, right);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Where n is the maximum value, we shift bits at most 32 times for 32-bit integers

⚡ Linearithmic

Space Complexity

O(1)

Only use constant extra space for shift counter

✓ Linear Space

267.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Common Prefix Method — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler