Coding Interview Patterns Module 17 – Bit manipulation
Bitwise AND of a range: powers of two, reversal
The bitwise AND of every integer in a range, the next power of two for a buffer and a word with its bits reversed: the problems and the brute force.
What you will learn
- Compute the AND of every integer from m to n from their common binary prefix
- Prove that the AND of a range keeps only the bits above the highest difference
- Test for a power of two and find the next one for a buffer size
- Find the highest 1 bit in each of the 14 languages, with a built-in where there is one
- Rotate and reverse the 32 bits of a word with masks and with built-ins
Before you start
What you’ll learn · Before you start
What you will learn
- Compute the AND of every integer from m to n from their common binary prefix
- Prove that the AND of a range keeps only the bits above the highest difference
- Test for a power of two and find the next one for a buffer size
- Find the highest 1 bit in each of the 14 languages, with a built-in where there is one
- Rotate and reverse the 32 bits of a word with masks and with built-ins
Before you start
On this page
The bitwise AND of a range of integers keeps a bit only if every number from m to n has it, so any bit that changes somewhere inside the range comes out 0: the AND of 26 to 30 is 24. Interviews ask for it because the obvious loop over the range is hopeless at 2³¹ numbers, while the answer takes at most 32 steps. Two related questions ask where a number’s bits are: whether a size is a power of two and which power comes next, and what a word is with its 32 bits reversed. All three follow, each with its brute force and the signal for the fast method.
Three problems about where the bits are
Problem A: the AND of a range. Answer up to 10⁵ queries, each a pair 0 ≤ m ≤ n ≤ 2³¹ − 1: return the bitwise AND of every integer from m to n.
(26, 30)gives 24, and(12, 15)gives 12.(5, 5)gives 5, and(1, 2147483647)gives 0.
The AND of the range 26 to 30
Text description of the diagram
The figure writes the numbers 26 to 30 as five bits each, worth 16, 8, 4, 2 and 1: 26 is 11010, 27 is 11011, 28 is 11100, 29 is 11101 and 30 is 11110.
The AND of the range has a 1 in a column only if every number has a 1 there. The 16s and 8s columns, highlighted, are 1 in all five numbers. The 4s column has 0s in 26 and 27, the 2s column a 0 in 28 and 29, and the 1s column 0s in 26, 28 and 30, so those three columns AND to 0. The result is 11000, which is 24.
Problem B: a buffer size. A recording app needs A buffer of fixed size whose write position wraps around to the start when it reaches the end, so the oldest data is overwritten first. whose size is a power of two: A number with exactly one 1 bit in its binary form, such as 1, 2, 4 or 1,024: 2 multiplied by itself some number of times.. For a request of r bytes, 1 ≤ r ≤ 2³⁰, say whether r is already a power of two and return the smallest power of two that is at least r: 1000 gives 1024, and 4096 gives 4096.
Problem C: a reversed word. A sensor sends 32-bit readings with the bit order reversed. Return each reading with its 32 bits reversed, as an unsigned number: 11, which is 1011, gives 3,489,660,928, which is 1101 followed by 28 zeros.
Checkpoint
Check: The AND of a range, buffer sizes and reversed words
The brute force, and why it fails at these sizes
Problem A breaks, as the run’s last two lines show:
# The three problems by brute force. A: AND every integer of the range. B: double until the buffer is big enough.
# C: move the bits one at a time.
def range_and_brute(m, n):
"""Problem A: the AND of every integer from m to n, and the ANDs it took (it stops early at 0)."""
acc, steps = m, 0
for x in range(m + 1, n + 1):
if acc == 0:
break
acc &= x
steps += 1
return acc, steps
def buffer_size_brute(r):
"""Problem B: whether r is a power of two, and the smallest power of two that is at least r."""
size = 1
while size < r:
size *= 2
return size == r, size
def reverse_brute(x):
"""Problem C: the 32 bits of x in reverse order, one bit at a time."""
out = 0
for _ in range(32):
out = (out << 1) | (x & 1)
x >>= 1
return out
for m, n in ((26, 30), (12, 15), (5, 5), (1, 2**31 - 1)):
value, steps = range_and_brute(m, n)
print(f"A: AND of {m}..{n} = {value} ({steps} {'AND' if steps == 1 else 'ANDs'})")
for r in (1000, 4096, 1):
print(f"B: request {r}: {buffer_size_brute(r)}")
for x in (11, 1, 0):
print(f"C: reverse of {x} = {reverse_brute(x)}")
m, n = 2**30, 2**31 - 1
print(f"A on {m:,}..{n:,}: the AND never reaches 0, so {n - m:,} ANDs for one query")
print(f"with 100,000 such queries: {100_000 * (n - m):,} ANDs")Output
A: AND of 26..30 = 24 (4 ANDs) A: AND of 12..15 = 12 (3 ANDs) A: AND of 5..5 = 5 (0 ANDs) A: AND of 1..2147483647 = 0 (1 AND) B: request 1000: (False, 1024) B: request 4096: (True, 4096) B: request 1: (True, 1) C: reverse of 11 = 3489660928 C: reverse of 1 = 2147483648 C: reverse of 0 = 0 A on 1,073,741,824..2,147,483,647: the AND never reaches 0, so 1,073,741,823 ANDs for one query with 100,000 such queries: 107,374,182,300,000 ANDs
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 brute_force.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
ANDing every integer of the range can stop once the result is 0, which saves the
query (1, 2147483647), but (2³⁰, 2³¹ − 1) never reaches 0: 1,073,741,823 ANDs for one query, and 10⁵ such queries
need 107,374,182,300,000, about 12 days of computing even at 10⁸ ANDs a second. B and C are cheap even by brute force,
30 doublings and 32 bit moves at most, which is why their questions are about doing them in a few operations and
getting the edge cases right. Step through the brute force of A on its first query:
The drawing shows the whole scene; its 5 steps are listed below.
Every step as text
- The first number. The running AND starts as 26, which is 11010 in binary.
- AND 27. 27 is 11011. It has every 1 that 26 has, so the AND stays 11010, which is 26.
- AND 28. 28 is 11100, with a 0 in bit 1, so bit 1 drops out and the AND becomes 11000, which is 24.
- AND 29. 29 is 11101. Bits 4 and 3 are still on in it, so the AND stays 11000.
- AND 30. 30 is 11110, and the AND is still 11000 = 24. Only the bits above the highest difference of 26 and 30 survived, and the loop took 4 ANDs for 5 numbers; for a range of 2³⁰ numbers it would take more than a billion.
Checkpoint
Check: What the brute force costs at the limits
What to notice
- In A, a bit that flips anywhere in the range is 0 in the AND, and once the numbers differ at some bit, every lower bit flips on the way from m to n. Only the bits above the highest difference of m and n can survive.
- In B, a power of two has exactly one 1 bit, and the next power of two depends only on the length of r − 1 in binary.
- In C, the reversal is a fixed reordering of 32 positions, so it can move blocks of bits instead of single bits.
Step through them on small cases:
The drawing shows the whole scene; its 3 steps are listed below.
Every step as text
- Where the ends differ. 26 is 11010 and 30 is 11110. They agree on the top two bits, 11, and first differ at bit 2. Every number from 26 to 30 starts with 11, and each lower bit is 0 in at least one of them, so only the 11 can survive in the AND.
- One 1 bit, and a length. 64 is 1000000, a single 1 bit, as in every power of two. For a request of 1000, 999 is 1111100111, 10 bits long, so the smallest power of two that is at least 1000 is 2¹⁰ = 1024.
- The same moves for every word. Reversing 32 bits sends bit i to bit 31 − i whatever the value, so 11, which is 1011, becomes 1101 followed by 28 zeros. The moves never depend on the bits themselves, so whole blocks of bits can move together.
Checkpoint
Check: The signals that point to the fast methods
The questions below cover the three problems and their brute force, the one you know least first.
Practice that adapts to you
Practise this lesson
9 questions about 9 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
The common prefix: why the AND keeps only the shared high bits Pro: opens with a Pro, Premium or Ultimate pass
- Three ways to find it, each traced on 26 to 30
- Powers of two: the test, the next one and the highest 1 bit
- Reversing and rotating 32 bits
- The code in 14 languages
- IP address ranges: the AND as a network address
- Edge cases and common bugs
- Variants: the OR of a range, powers of four and aligned sizes
- Exercise: the AND of a range and a reversed word
- The AND of a range, and a word reversed
- A practice set with sample answers
- Interview questions
- Why is the AND of every integer from m to n equal to the common binary prefix of m and n, followed by zeros?
- Given the first and last IPv4 address of a range, return the smallest CIDR block that holds both. Your Java version keeps addresses in int, clears the lowest bit of n while n > m, and returns a wrong block for some ranges. Which ranges, why, and how do you fix it?
- Write next_power_of_two(r) for buffer sizes in Java or C++. What should it return for r = 0, r = 1, r = 2^30 + 1 and r = 2^31, and what does a typical one-line version actually return for each?
- A decoder must reverse the bit order of 10^8 32-bit words. Compare a 32-step loop, five mask-and-shift swaps, a 256-entry byte table and the built-ins of Java and Go. Which do you choose, and what would you measure before deciding?
- Key takeaways
3 diagrams · 8 runnable examples (Java, Python) · 1 exercise with sample tests · 3 interview answers · about 36 minutes
Opening this part with your pass…
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Terms in this lesson
- power of two
- A number with exactly one 1 bit in its binary form, such as 1, 2, 4 or 1,024: 2 multiplied by itself some number of times.
References
- Additional methods on integer types: int.bit_length() (The Python Standard Library: built-in types) (Python Software Foundation)
- ipaddress: IPv4/IPv6 manipulation library (The Python Standard Library) (Python Software Foundation)
- Java SE 25 API: Integer (reverse, numberOfLeadingZeros, highestOneBit, compareUnsigned) (Oracle)
- std::bit_ceil (cppreference.com) (cppreference.com)
- std::has_single_bit (cppreference.com) (cppreference.com)
- Package bits (math/bits): Len32 and Reverse32 (The Go Authors)
- ECMAScript language specification: Math.clz32 (Ecma International (TC39))
- RFC 4632: Classless Inter-domain Routing (CIDR): the Internet Address Assignment and Aggregation Plan (IETF)
- BitOperations class (.NET API): IsPow2, RoundUpToPowerOf2, LeadingZeroCount (Microsoft)
- Primitive type u32 (Rust standard library): next_power_of_two, is_power_of_two, reverse_bits (The Rust Project)
- FixedWidthInteger.leadingZeroBitCount (Swift standard library) (Apple)
- countLeadingZeroBits (Kotlin standard library) (JetBrains (Kotlin))
- Int.shl (Kotlin standard library) (JetBrains (Kotlin))
- Class Integer (Ruby 4.0 documentation): bit_length (Ruby (ruby-lang.org))
- Integers (PHP manual): size and integer overflow (The PHP Group)
- Numbers in Dart (Dart (Google))
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress