Problem editorial

Bitwise AND of Numbers Range

MediumBit Manipulation PatternsBit ManipulationMathIteration

Bitwise AND of Numbers Range: the approach in brief

The problem

Given two non-negative integers left and right, consider every integer in the inclusive range from left through right. The bitwise AND of two integers keeps a bit set only when that bit is set in both integers; applying it across a collection means every bit must be set in every value.

Pattern

Bitwise AND of Numbers Range is a Bit Manipulation Patterns problem, in the Bitwise Operations - Power of Two/Four Check subpattern. The pattern covers xOR tricks, counting bits, power-of-two checks, and Hamming weight

Approach outline

The range can be very large, so avoid visiting every integer individually.
A bit can remain set in the result only if it is set in both endpoints and in every value between them.
Incrementing through a range eventually changes lower-order bits and may carry into higher-order bits.

Complexity

The reference solution runs in O(log right), at most 31 iterations time and O(1) space.

The full editorial is part of Pro

It explains the core insight, the complexity analysis and the common mistakes, with a worked solution.

Unlock the full editorial with Pro Solve it first, free

Practise Bitwise AND of Numbers Range and the problems around it

Bitwise AND of Numbers Range is a Bit Manipulation Patterns problem, in the Bitwise Operations - Power of Two/Four Check subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Bitwise AND of Numbers Range