Bitwise AND of Numbers Range
Bitwise AND of Numbers Range is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Bit Manipulation Patterns pattern, in the Bitwise Operations - Power of Two/Four Check subpattern.
Problem statement
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.
Return the single integer produced by bitwise-ANDing all integers in that range. The range may contain just one value, in which case return that value unchanged.
Example 1:
Input: left = 26, right = 30 Output: 24 Explanation: All values from 26 through 30 share only the bit pattern represented by 24, so the combined AND is 24.
Example 2:
Input: left = 7, right = 7 Output: 7 Explanation: The range contains one integer, so its bitwise AND is 7 itself.
Example 3:
Input: left = 8, right = 11 Output: 8 Explanation: The values 8, 9, 10, and 11 all retain the highest bit of 8, while lower bits are not set in every value.
Constraints:
- 0 <= left - left <= right - right <= 2^31 - 1
Topics and companies
Topics: Bit Manipulation, Math, Iteration.
How to practise Bitwise AND of Numbers Range on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(log right), at most 31 iterations time and O(1) space.
Open Bitwise AND of Numbers Range in the code editor, or read the Bitwise AND of Numbers Range editorial for a worked solution with its approach and complexity analysis.
Where Bitwise AND of Numbers Range sits in the DSA pattern sheet
- Bit Manipulation Patterns pattern guide
- Bitwise Operations - Power of Two/Four Check subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Bitwise AND of Numbers Range
Other problems that use the same Bitwise Operations - Power of Two/Four Check and Bit Manipulation Patterns techniques:
- Minimum Array End — Medium, same subpattern
- Power of Four — Easy, same subpattern
- Pow(x, n) — Medium, same subpattern
- Counting Bits — Easy, same pattern
- Find the Difference — Easy, same pattern
- Missing Number — Easy, same pattern