Bitwise AND of Range

medium

Find bitwise AND of all numbers in range [left, right]

Bitwise AND of Range

Key Insight

Find common prefix of left and right. Bits that differ will become 0.

Step 1Problem
5
5
=
0
0
0
0
0
1
0
1
6
6
=
0
0
0
0
0
1
1
0
7
7
=
0
0
0
0
0
1
1
1
76543210

AND all numbers from 5 to 7.

1 / 5

Learn the Pattern

Bit ManipulationUse bitwise operations to solve problems efficiently by treating integers as arrays of bits.
Practice the Code

Step-by-Step Walkthrough: Bitwise AND of Range

Find common prefix of left and right. Bits that differ will become 0.

  1. Problem

    AND all numbers from 5 to 7.

  2. Compare Endpoints

    5=101, 7=111. Find common prefix.

  3. Right Shift Both

    Shift until left == right.

  4. Found Prefix

    2>>1=1, 3>>1=1. Same! Shift back.

  5. Result

    1 << 2 = 4. AND of 5..7 is 4!