What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Bit Manipulation

Builds on Bit Tricks, which you haven’t finished yet.

P2MediumBuilt on Bit Tricks~3 min speedrun

Shared Binary Prefix (Bitwise AND of Numbers Range)

Built on

Bit TricksShift two numbers right together until they are equal, count the shifts in shift, then shift the equal value back left by shift.

The problem

Bitwise AND of Numbers Range (LC 201)(opens leetcode.com)

You get two integers, left and right, with left <= right. Take every integer from left up to right, including both ends. Combine all of them with the bitwise AND operator. Bitwise AND compares numbers bit by bit and keeps a bit only when every number has a 1 in that place.

Return that single result.

Example 1

Input:left = 5, right = 7

Output:4

The numbers are 5 (101), 6 (110) and 7 (111). The top bit is 1 in all three, and each of the two lower bits is 0 in at least one of them. So the AND is 100, which is 4.

Shared Prefix

left, right ➔ shift both right until equal, counting shift ➔ shared prefix << shift

Spot it when: You must combine every integer between two bounds with AND, or find the leading bits that two numbers share.

Shared Prefix

Python

1	def range_bitwise_and(left: int, right: int) -> int:
2	"""Bitwise AND of Numbers Range: the shared binary prefix of the two ends, followed by zeros.
3	Time: O(log right) \| Space: O(1)
4	"""
5	# shift: how many low bits have been removed from both ends so far
6	shift = 0
7
8	# 1. Shift Both Ends Right Until They Are Equal:
9	# Every bit below the highest place where the ends differ is 0 in some number of the range, so it cannot survive the AND.
10	# Removing the lowest bit of both ends together keeps their shared prefix and counts how many bits were removed.
11	while left != right:
12	left >>= 1
13	right >>= 1
14	shift += 1
15
16	# 2. Shift The Shared Prefix Back:
17	# The equal value is the prefix. Shifting it left by shift puts it in its original place with zeros below.
18	return left << shift

Invariant: left and right are the original ends with their lowest shift bits removed, and their shared prefix is the shared prefix of the original ends.

Only the binary prefix that left and right share can survive the AND, so shift both right until they are equal and count the shifts in shift. Counting up from left to right passes the number prefix followed by 0111...1 and then the next number, prefix followed by 1000...0. These two numbers have no 1 bit in common below the prefix, so every lower bit is cleared, while every number in the range keeps the prefix. After the loop, left holds only the prefix, so return left << shift, not left: for left = 5 and right = 7 the loop ends with left = 1 and shift = 2, and 1 is wrong where 1 << 2 = 4 is right.

See it run

Bitwise AND of Numbers Range, step by step

left 22right 30shift 0

The top row is left, the middle row is right and the bottom row is the returned value. Each column is one bit position, with the highest position on the left.

drop the lowest bit that the next round removes
equal the shared prefix, once left and right are the same
written the returned value, left << shift

Start: left = 22 is 00010110 and right = 30 is 00011110. shift = 0.

left

right

result

1 / 13

Gotchas1 of 4

The trap
Gotcha 1: Returning left without shifting it back
Mistake
```
return left
```
Fix
```
return left << shift
```
What happens: After the loop, left and right hold only the shared prefix, with shift low bits removed. return left gives that short number. The answer needs the same prefix in its original place, with shift zeros below it, so the right answer is 2 ** shift times larger.
Example: Bitwise AND of Numbers Range (LC 201): left = 5, right = 7
Mistake: returns 1Fix: returns 4
Gotcha 2: Returning left & right of the two ends
Mistake
```
return left & right
```
Fix
```
return left << shift
```
What happens: left & right only looks at the two ends. A number between them can have a 0 in a place where both ends have a 1, and then the AND of the whole range clears that bit. For 5 (101) and 7 (111), the number 6 (110) clears bit 0, which both ends have set.
Example: Bitwise AND of Numbers Range (LC 201): left = 5, right = 7
Mistake: returns 5Fix: returns 4
Gotcha 3: Shifting only right in the loop
Mistake
```
right >>= 1
```
Fix
```
left >>= 1
right >>= 1
```
What happens: The loop stops when left equals right. If only right is shifted, it falls toward 0 while left stays the same. When left is larger than 0, right never becomes equal to it, so the loop never ends.
Example: Bitwise AND of Numbers Range (LC 201): left = 5, right = 7
Mistake: the loop never endsFix: returns 4
Gotcha 4: Looping over every number of the range with a running AND
What happens: for value in range(left, right + 1): result &= value gives the right answer, but the range can hold about 2 billion numbers. The shift loop runs at most 31 times, because each round removes one bit from both ends.

Not this one if…

The result is built from both numbers bit by bit, such as the sum with carries in Sum of Two Integers (LC 371), not only from the leading bits that they share. See Carry Add
The input is one number whose 1 bits you count or clear, as in Number of 1 Bits (LC 191), not the two ends of a range. See Kernighan's Bit Trick

Deep Dive

Why only the shared prefix survives the AND

Bit Tricks already taught the shift and the mask. This card adds one idea: the AND of a whole range is the binary prefix that left and right share, followed by zeros.

Take left = 22 and right = 30. In 8 bits, 22 is 00010110 and 30 is 00011110. They agree on the bits at positions 7 to 4, and the highest position where they differ is position 3.

Counting up from 22 to 30 must pass a number with the shared prefix followed by 0111...1 and then the next number, the shared prefix followed by 1000...0. Here those two numbers are 23 (00010111) and 24 (00011000). They have no 1 bit in common below the prefix. So the AND of the range has a 0 in every position below the prefix.

Every number in the range keeps the prefix, because counting up from 22 to 30 never changes the bits above position 3. The AND of the range of 22 to 30 is therefore 00010000, which is 16. I checked this against a loop that ANDs every number from 22 to 30, and the result is 16.

What the shift loop does, round by round

The loop while left != right removes the lowest bit of both numbers with left >>= 1 and right >>= 1. It adds 1 to shift each time.

For left = 22 and right = 30, the pairs are (22, 30), (11, 15), (5, 7), (2, 3) and (1, 1). That is 4 rounds, so shift = 4. The loop ends because left and right are both 1.

The final left is the shared prefix without its trailing zeros. To put it back in place, the function returns left << shift, which is 1 << 4 = 16.

The number of rounds equals the number of bits in left ^ right. For 22 ^ 30 = 8, that is 4 bits. The XOR of the two ends has its highest 1 bit exactly where they first differ. So the loop removes every bit from that position down.

The cost and the edge cases

Each round removes one bit from both numbers, so the loop runs at most as many times as the larger number has bits. For a 31-bit input, that is at most 31 rounds. The time is O(log right) and the space is O(1).

A loop over every number of the range gives the same answer, but the range can hold about 2 billion numbers. The shift loop does not depend on the length of the range.

Edge cases: when left == right, the loop does not run and the answer is left. For left = 0 and right = 0 the answer is 0. For left = 1 and right = 2147483647, the two ends share no prefix, the loop runs 31 times, and the answer is 0. For left = 7 and right = 8, which are 0111 and 1000, the answer is also 0.

There is a second way to get the same result: while right > left: right &= right - 1, then return right. Each step clears the lowest 1 bit of right, as in Kernighan's Bit Trick. I compared it with the shift loop on 50,000 random pairs, and the answers matched.

60-Second Pitch

"The AND of a range keeps only the leading bits that every number in the range shares. Below the first position where left and right differ, the range contains a number ending in 0111...1 and the next number ending in 1000...0. So every lower bit becomes 0. I find the shared prefix by shifting left and right right together until they are equal, and I count the shifts in shift. Then I return left << shift, so the prefix goes back to its original place. For 22 to 30, the loop runs 4 times, and the answer is 1 shifted left by 4, which is 16. The loop runs at most 31 times, so the time is O(log right) and the space is O(1)."

Common Questions

What is the time and space complexity?: O(log right) time and O(1) space. Each round removes one bit from both numbers, so there are at most 31 rounds for a 31-bit input. The length of the range does not matter.
Why is left & right of the two ends not enough?: A number between the ends can clear a bit that both ends have set. For left = 22 and right = 30, the ends give 22, but 23 and 24 have no 1 bit in common below the prefix, so the range gives 16.
What happens when left equals right?: The loop does not run. shift stays 0, and the function returns left << 0, which is left. That is correct, because the range holds one number.
Is there a version without a shift counter?: Yes. Use while right > left: right &= right - 1, then return right. Each step clears the lowest 1 bit of right. When right is no longer larger than left, the remaining 1 bits are the shared prefix. It gives the same answers as the shift loop.
How does this differ from Sum of Two Integers (LC 371)?: Here the answer uses only the leading bits that the two numbers share. In Sum of Two Integers (LC 371), the answer is built from both numbers bit by bit, with carries, so no bit can be ignored.

SWE Reasoning

Spot it

The statement asks for the bitwise AND of every integer between two bounds, inclusive.
The range can be as large as 2 billion numbers, so a loop over the range is too slow.
The statement asks for the common leading bits of two numbers, or the longest shared binary prefix.
A small example by hand shows that the answer is always prefix followed by zeros.

The invariant, step by step

Start with shift = 0. left and right are the original ends.
A round runs left >>= 1, right >>= 1 and shift += 1. Now left and right are the original ends with their lowest shift bits removed.
Removing the same number of low bits from both ends keeps their shared prefix. It does not matter which low bits were removed.
The loop stops when left == right. At that moment the value is exactly the shared prefix of the original ends.
Every bit below the prefix is 0 in the AND, because the range contains the number prefix followed by 0111...1 and the number prefix followed by 1000...0.
left << shift puts the prefix back in its original place with shift zeros below it. That is the answer.

Traps

return left without << shift. The result is the prefix without its trailing zeros. For left = 5 and right = 7, it returns 1 instead of 4. For left = 22 and right = 30, it returns 1 instead of 16.
return left & right of the two ends. A number inside the range can have a 0 where both ends have a 1. For left = 22 and right = 30, this returns 22, but the right answer is 16.
Shifting only right. left never changes, so for left > 0 the two values may never become equal. The loop does not end.
Looping over the whole range with result &= value. The answer is right, but the range can hold about 2 billion numbers, so the solution is too slow.

Practice

Canonical LeetCode:Bitwise AND of Numbers Range (LC 201)

Theory Context•Bit Manipulation

Builds on Bit Tricks, which you haven’t finished yet.

P2MediumBuilt on Bit Tricks~3 min speedrun

Shared Binary Prefix (Bitwise AND of Numbers Range)

Built on

Bit TricksShift two numbers right together until they are equal, count the shifts in shift, then shift the equal value back left by shift.

The problem

Bitwise AND of Numbers Range (LC 201)(opens leetcode.com)

Return that single result.

Example 1

Input:left = 5, right = 7

Output:4

The numbers are 5 (101), 6 (110) and 7 (111). The top bit is 1 in all three, and each of the two lower bits is 0 in at least one of them. So the AND is 100, which is 4.

Shared Prefix

left, right ➔ shift both right until equal, counting shift ➔ shared prefix << shift

Spot it when: You must combine every integer between two bounds with AND, or find the leading bits that two numbers share.

Shared Prefix

Python

1	def range_bitwise_and(left: int, right: int) -> int:
2	"""Bitwise AND of Numbers Range: the shared binary prefix of the two ends, followed by zeros.
3	Time: O(log right) \| Space: O(1)
4	"""
5	# shift: how many low bits have been removed from both ends so far
6	shift = 0
7
8	# 1. Shift Both Ends Right Until They Are Equal:
9	# Every bit below the highest place where the ends differ is 0 in some number of the range, so it cannot survive the AND.
10	# Removing the lowest bit of both ends together keeps their shared prefix and counts how many bits were removed.
11	while left != right:
12	left >>= 1
13	right >>= 1
14	shift += 1
15
16	# 2. Shift The Shared Prefix Back:
17	# The equal value is the prefix. Shifting it left by shift puts it in its original place with zeros below.
18	return left << shift

Invariant: left and right are the original ends with their lowest shift bits removed, and their shared prefix is the shared prefix of the original ends.

See it run

Bitwise AND of Numbers Range, step by step

left 22right 30shift 0

The top row is left, the middle row is right and the bottom row is the returned value. Each column is one bit position, with the highest position on the left.

drop the lowest bit that the next round removes
equal the shared prefix, once left and right are the same
written the returned value, left << shift

Start: left = 22 is 00010110 and right = 30 is 00011110. shift = 0.

left

right

result

1 / 13

Gotchas1 of 4

The trap
Gotcha 1: Returning left without shifting it back
Mistake
```
return left
```
Fix
```
return left << shift
```
What happens: After the loop, left and right hold only the shared prefix, with shift low bits removed. return left gives that short number. The answer needs the same prefix in its original place, with shift zeros below it, so the right answer is 2 ** shift times larger.
Example: Bitwise AND of Numbers Range (LC 201): left = 5, right = 7
Mistake: returns 1Fix: returns 4
Gotcha 2: Returning left & right of the two ends
Mistake
```
return left & right
```
Fix
```
return left << shift
```
What happens: left & right only looks at the two ends. A number between them can have a 0 in a place where both ends have a 1, and then the AND of the whole range clears that bit. For 5 (101) and 7 (111), the number 6 (110) clears bit 0, which both ends have set.
Example: Bitwise AND of Numbers Range (LC 201): left = 5, right = 7
Mistake: returns 5Fix: returns 4
Gotcha 3: Shifting only right in the loop
Mistake
```
right >>= 1
```
Fix
```
left >>= 1
right >>= 1
```
What happens: The loop stops when left equals right. If only right is shifted, it falls toward 0 while left stays the same. When left is larger than 0, right never becomes equal to it, so the loop never ends.
Example: Bitwise AND of Numbers Range (LC 201): left = 5, right = 7
Mistake: the loop never endsFix: returns 4
Gotcha 4: Looping over every number of the range with a running AND
What happens: for value in range(left, right + 1): result &= value gives the right answer, but the range can hold about 2 billion numbers. The shift loop runs at most 31 times, because each round removes one bit from both ends.

Not this one if…

The result is built from both numbers bit by bit, such as the sum with carries in Sum of Two Integers (LC 371), not only from the leading bits that they share. See Carry Add
The input is one number whose 1 bits you count or clear, as in Number of 1 Bits (LC 191), not the two ends of a range. See Kernighan's Bit Trick

Deep Dive

Why only the shared prefix survives the AND

Bit Tricks already taught the shift and the mask. This card adds one idea: the AND of a whole range is the binary prefix that left and right share, followed by zeros.

Take left = 22 and right = 30. In 8 bits, 22 is 00010110 and 30 is 00011110. They agree on the bits at positions 7 to 4, and the highest position where they differ is position 3.

What the shift loop does, round by round

The loop while left != right removes the lowest bit of both numbers with left >>= 1 and right >>= 1. It adds 1 to shift each time.

For left = 22 and right = 30, the pairs are (22, 30), (11, 15), (5, 7), (2, 3) and (1, 1). That is 4 rounds, so shift = 4. The loop ends because left and right are both 1.

The final left is the shared prefix without its trailing zeros. To put it back in place, the function returns left << shift, which is 1 << 4 = 16.

The cost and the edge cases

A loop over every number of the range gives the same answer, but the range can hold about 2 billion numbers. The shift loop does not depend on the length of the range.

60-Second Pitch

Common Questions

What is the time and space complexity?: O(log right) time and O(1) space. Each round removes one bit from both numbers, so there are at most 31 rounds for a 31-bit input. The length of the range does not matter.
Why is left & right of the two ends not enough?: A number between the ends can clear a bit that both ends have set. For left = 22 and right = 30, the ends give 22, but 23 and 24 have no 1 bit in common below the prefix, so the range gives 16.
What happens when left equals right?: The loop does not run. shift stays 0, and the function returns left << 0, which is left. That is correct, because the range holds one number.
Is there a version without a shift counter?: Yes. Use while right > left: right &= right - 1, then return right. Each step clears the lowest 1 bit of right. When right is no longer larger than left, the remaining 1 bits are the shared prefix. It gives the same answers as the shift loop.
How does this differ from Sum of Two Integers (LC 371)?: Here the answer uses only the leading bits that the two numbers share. In Sum of Two Integers (LC 371), the answer is built from both numbers bit by bit, with carries, so no bit can be ignored.

SWE Reasoning

Spot it

The statement asks for the bitwise AND of every integer between two bounds, inclusive.
The range can be as large as 2 billion numbers, so a loop over the range is too slow.
The statement asks for the common leading bits of two numbers, or the longest shared binary prefix.
A small example by hand shows that the answer is always prefix followed by zeros.

The invariant, step by step

Start with shift = 0. left and right are the original ends.
A round runs left >>= 1, right >>= 1 and shift += 1. Now left and right are the original ends with their lowest shift bits removed.
Removing the same number of low bits from both ends keeps their shared prefix. It does not matter which low bits were removed.
The loop stops when left == right. At that moment the value is exactly the shared prefix of the original ends.
Every bit below the prefix is 0 in the AND, because the range contains the number prefix followed by 0111...1 and the number prefix followed by 1000...0.
left << shift puts the prefix back in its original place with shift zeros below it. That is the answer.

Traps

return left without << shift. The result is the prefix without its trailing zeros. For left = 5 and right = 7, it returns 1 instead of 4. For left = 22 and right = 30, it returns 1 instead of 16.
return left & right of the two ends. A number inside the range can have a 0 where both ends have a 1. For left = 22 and right = 30, this returns 22, but the right answer is 16.
Shifting only right. left never changes, so for left > 0 the two values may never become equal. The loop does not end.
Looping over the whole range with result &= value. The answer is right, but the range can hold about 2 billion numbers, so the solution is too slow.

Practice

Canonical LeetCode:Bitwise AND of Numbers Range (LC 201)

Theory Context•Bit Manipulation

Builds on Bit Tricks, which you haven’t finished yet.

P2MediumBuilt on Bit Tricks~3 min speedrun

Shared Binary Prefix (Bitwise AND of Numbers Range)

Built on

Bit TricksShift two numbers right together until they are equal, count the shifts in shift, then shift the equal value back left by shift.

The problem

Bitwise AND of Numbers Range (LC 201)(opens leetcode.com)

Return that single result.

Example 1

Input:left = 5, right = 7

Output:4

The numbers are 5 (101), 6 (110) and 7 (111). The top bit is 1 in all three, and each of the two lower bits is 0 in at least one of them. So the AND is 100, which is 4.

Shared Prefix

left, right ➔ shift both right until equal, counting shift ➔ shared prefix << shift

Spot it when: You must combine every integer between two bounds with AND, or find the leading bits that two numbers share.

Shared Prefix

Python

1	def range_bitwise_and(left: int, right: int) -> int:
2	"""Bitwise AND of Numbers Range: the shared binary prefix of the two ends, followed by zeros.
3	Time: O(log right) \| Space: O(1)
4	"""
5	# shift: how many low bits have been removed from both ends so far
6	shift = 0
7
8	# 1. Shift Both Ends Right Until They Are Equal:
9	# Every bit below the highest place where the ends differ is 0 in some number of the range, so it cannot survive the AND.
10	# Removing the lowest bit of both ends together keeps their shared prefix and counts how many bits were removed.
11	while left != right:
12	left >>= 1
13	right >>= 1
14	shift += 1
15
16	# 2. Shift The Shared Prefix Back:
17	# The equal value is the prefix. Shifting it left by shift puts it in its original place with zeros below.
18	return left << shift

Invariant: left and right are the original ends with their lowest shift bits removed, and their shared prefix is the shared prefix of the original ends.

See it run

Bitwise AND of Numbers Range, step by step

left 22right 30shift 0

The top row is left, the middle row is right and the bottom row is the returned value. Each column is one bit position, with the highest position on the left.

drop the lowest bit that the next round removes
equal the shared prefix, once left and right are the same
written the returned value, left << shift

Start: left = 22 is 00010110 and right = 30 is 00011110. shift = 0.

left

right

result

1 / 13

Gotchas1 of 4

The trap
Gotcha 1: Returning left without shifting it back
Mistake
```
return left
```
Fix
```
return left << shift
```
What happens: After the loop, left and right hold only the shared prefix, with shift low bits removed. return left gives that short number. The answer needs the same prefix in its original place, with shift zeros below it, so the right answer is 2 ** shift times larger.
Example: Bitwise AND of Numbers Range (LC 201): left = 5, right = 7
Mistake: returns 1Fix: returns 4
Gotcha 2: Returning left & right of the two ends
Mistake
```
return left & right
```
Fix
```
return left << shift
```
What happens: left & right only looks at the two ends. A number between them can have a 0 in a place where both ends have a 1, and then the AND of the whole range clears that bit. For 5 (101) and 7 (111), the number 6 (110) clears bit 0, which both ends have set.
Example: Bitwise AND of Numbers Range (LC 201): left = 5, right = 7
Mistake: returns 5Fix: returns 4
Gotcha 3: Shifting only right in the loop
Mistake
```
right >>= 1
```
Fix
```
left >>= 1
right >>= 1
```
What happens: The loop stops when left equals right. If only right is shifted, it falls toward 0 while left stays the same. When left is larger than 0, right never becomes equal to it, so the loop never ends.
Example: Bitwise AND of Numbers Range (LC 201): left = 5, right = 7
Mistake: the loop never endsFix: returns 4
Gotcha 4: Looping over every number of the range with a running AND
What happens: for value in range(left, right + 1): result &= value gives the right answer, but the range can hold about 2 billion numbers. The shift loop runs at most 31 times, because each round removes one bit from both ends.

Not this one if…

The result is built from both numbers bit by bit, such as the sum with carries in Sum of Two Integers (LC 371), not only from the leading bits that they share. See Carry Add
The input is one number whose 1 bits you count or clear, as in Number of 1 Bits (LC 191), not the two ends of a range. See Kernighan's Bit Trick

Deep Dive

Why only the shared prefix survives the AND

Bit Tricks already taught the shift and the mask. This card adds one idea: the AND of a whole range is the binary prefix that left and right share, followed by zeros.

Take left = 22 and right = 30. In 8 bits, 22 is 00010110 and 30 is 00011110. They agree on the bits at positions 7 to 4, and the highest position where they differ is position 3.

What the shift loop does, round by round

The loop while left != right removes the lowest bit of both numbers with left >>= 1 and right >>= 1. It adds 1 to shift each time.

For left = 22 and right = 30, the pairs are (22, 30), (11, 15), (5, 7), (2, 3) and (1, 1). That is 4 rounds, so shift = 4. The loop ends because left and right are both 1.

The final left is the shared prefix without its trailing zeros. To put it back in place, the function returns left << shift, which is 1 << 4 = 16.

The cost and the edge cases

A loop over every number of the range gives the same answer, but the range can hold about 2 billion numbers. The shift loop does not depend on the length of the range.

60-Second Pitch

Common Questions

What is the time and space complexity?: O(log right) time and O(1) space. Each round removes one bit from both numbers, so there are at most 31 rounds for a 31-bit input. The length of the range does not matter.
Why is left & right of the two ends not enough?: A number between the ends can clear a bit that both ends have set. For left = 22 and right = 30, the ends give 22, but 23 and 24 have no 1 bit in common below the prefix, so the range gives 16.
What happens when left equals right?: The loop does not run. shift stays 0, and the function returns left << 0, which is left. That is correct, because the range holds one number.
Is there a version without a shift counter?: Yes. Use while right > left: right &= right - 1, then return right. Each step clears the lowest 1 bit of right. When right is no longer larger than left, the remaining 1 bits are the shared prefix. It gives the same answers as the shift loop.
How does this differ from Sum of Two Integers (LC 371)?: Here the answer uses only the leading bits that the two numbers share. In Sum of Two Integers (LC 371), the answer is built from both numbers bit by bit, with carries, so no bit can be ignored.

SWE Reasoning

Spot it

The statement asks for the bitwise AND of every integer between two bounds, inclusive.
The range can be as large as 2 billion numbers, so a loop over the range is too slow.
The statement asks for the common leading bits of two numbers, or the longest shared binary prefix.
A small example by hand shows that the answer is always prefix followed by zeros.

The invariant, step by step

Start with shift = 0. left and right are the original ends.
A round runs left >>= 1, right >>= 1 and shift += 1. Now left and right are the original ends with their lowest shift bits removed.
Removing the same number of low bits from both ends keeps their shared prefix. It does not matter which low bits were removed.
The loop stops when left == right. At that moment the value is exactly the shared prefix of the original ends.
Every bit below the prefix is 0 in the AND, because the range contains the number prefix followed by 0111...1 and the number prefix followed by 1000...0.
left << shift puts the prefix back in its original place with shift zeros below it. That is the answer.

Traps

return left without << shift. The result is the prefix without its trailing zeros. For left = 5 and right = 7, it returns 1 instead of 4. For left = 22 and right = 30, it returns 1 instead of 16.
return left & right of the two ends. A number inside the range can have a 0 where both ends have a 1. For left = 22 and right = 30, this returns 22, but the right answer is 16.
Shifting only right. left never changes, so for left > 0 the two values may never become equal. The loop does not end.
Looping over the whole range with result &= value. The answer is right, but the range can hold about 2 billion numbers, so the solution is too slow.

Practice

Canonical LeetCode:Bitwise AND of Numbers Range (LC 201)

Theory Context•Bit Manipulation

Builds on Bit Tricks, which you haven’t finished yet.

P2MediumBuilt on Bit Tricks~3 min speedrun

Shared Binary Prefix (Bitwise AND of Numbers Range)

Built on

Bit TricksShift two numbers right together until they are equal, count the shifts in shift, then shift the equal value back left by shift.

The problem

Bitwise AND of Numbers Range (LC 201)(opens leetcode.com)

Return that single result.

Example 1

Input:left = 5, right = 7

Output:4

The numbers are 5 (101), 6 (110) and 7 (111). The top bit is 1 in all three, and each of the two lower bits is 0 in at least one of them. So the AND is 100, which is 4.

Shared Prefix

left, right ➔ shift both right until equal, counting shift ➔ shared prefix << shift

Spot it when: You must combine every integer between two bounds with AND, or find the leading bits that two numbers share.

Shared Prefix

Python

1	def range_bitwise_and(left: int, right: int) -> int:
2	"""Bitwise AND of Numbers Range: the shared binary prefix of the two ends, followed by zeros.
3	Time: O(log right) \| Space: O(1)
4	"""
5	# shift: how many low bits have been removed from both ends so far
6	shift = 0
7
8	# 1. Shift Both Ends Right Until They Are Equal:
9	# Every bit below the highest place where the ends differ is 0 in some number of the range, so it cannot survive the AND.
10	# Removing the lowest bit of both ends together keeps their shared prefix and counts how many bits were removed.
11	while left != right:
12	left >>= 1
13	right >>= 1
14	shift += 1
15
16	# 2. Shift The Shared Prefix Back:
17	# The equal value is the prefix. Shifting it left by shift puts it in its original place with zeros below.
18	return left << shift

Invariant: left and right are the original ends with their lowest shift bits removed, and their shared prefix is the shared prefix of the original ends.

See it run

Bitwise AND of Numbers Range, step by step

left 22right 30shift 0

The top row is left, the middle row is right and the bottom row is the returned value. Each column is one bit position, with the highest position on the left.

drop the lowest bit that the next round removes
equal the shared prefix, once left and right are the same
written the returned value, left << shift

Start: left = 22 is 00010110 and right = 30 is 00011110. shift = 0.

left

right

result

1 / 13

Gotchas1 of 4

The trap
Gotcha 1: Returning left without shifting it back
Mistake
```
return left
```
Fix
```
return left << shift
```
What happens: After the loop, left and right hold only the shared prefix, with shift low bits removed. return left gives that short number. The answer needs the same prefix in its original place, with shift zeros below it, so the right answer is 2 ** shift times larger.
Example: Bitwise AND of Numbers Range (LC 201): left = 5, right = 7
Mistake: returns 1Fix: returns 4
Gotcha 2: Returning left & right of the two ends
Mistake
```
return left & right
```
Fix
```
return left << shift
```
What happens: left & right only looks at the two ends. A number between them can have a 0 in a place where both ends have a 1, and then the AND of the whole range clears that bit. For 5 (101) and 7 (111), the number 6 (110) clears bit 0, which both ends have set.
Example: Bitwise AND of Numbers Range (LC 201): left = 5, right = 7
Mistake: returns 5Fix: returns 4
Gotcha 3: Shifting only right in the loop
Mistake
```
right >>= 1
```
Fix
```
left >>= 1
right >>= 1
```
What happens: The loop stops when left equals right. If only right is shifted, it falls toward 0 while left stays the same. When left is larger than 0, right never becomes equal to it, so the loop never ends.
Example: Bitwise AND of Numbers Range (LC 201): left = 5, right = 7
Mistake: the loop never endsFix: returns 4
Gotcha 4: Looping over every number of the range with a running AND
What happens: for value in range(left, right + 1): result &= value gives the right answer, but the range can hold about 2 billion numbers. The shift loop runs at most 31 times, because each round removes one bit from both ends.

Not this one if…

The result is built from both numbers bit by bit, such as the sum with carries in Sum of Two Integers (LC 371), not only from the leading bits that they share. See Carry Add
The input is one number whose 1 bits you count or clear, as in Number of 1 Bits (LC 191), not the two ends of a range. See Kernighan's Bit Trick

Deep Dive

Why only the shared prefix survives the AND

Bit Tricks already taught the shift and the mask. This card adds one idea: the AND of a whole range is the binary prefix that left and right share, followed by zeros.

Take left = 22 and right = 30. In 8 bits, 22 is 00010110 and 30 is 00011110. They agree on the bits at positions 7 to 4, and the highest position where they differ is position 3.

What the shift loop does, round by round

The loop while left != right removes the lowest bit of both numbers with left >>= 1 and right >>= 1. It adds 1 to shift each time.

For left = 22 and right = 30, the pairs are (22, 30), (11, 15), (5, 7), (2, 3) and (1, 1). That is 4 rounds, so shift = 4. The loop ends because left and right are both 1.

The final left is the shared prefix without its trailing zeros. To put it back in place, the function returns left << shift, which is 1 << 4 = 16.

The cost and the edge cases

A loop over every number of the range gives the same answer, but the range can hold about 2 billion numbers. The shift loop does not depend on the length of the range.

60-Second Pitch

Common Questions

What is the time and space complexity?: O(log right) time and O(1) space. Each round removes one bit from both numbers, so there are at most 31 rounds for a 31-bit input. The length of the range does not matter.
Why is left & right of the two ends not enough?: A number between the ends can clear a bit that both ends have set. For left = 22 and right = 30, the ends give 22, but 23 and 24 have no 1 bit in common below the prefix, so the range gives 16.
What happens when left equals right?: The loop does not run. shift stays 0, and the function returns left << 0, which is left. That is correct, because the range holds one number.
Is there a version without a shift counter?: Yes. Use while right > left: right &= right - 1, then return right. Each step clears the lowest 1 bit of right. When right is no longer larger than left, the remaining 1 bits are the shared prefix. It gives the same answers as the shift loop.
How does this differ from Sum of Two Integers (LC 371)?: Here the answer uses only the leading bits that the two numbers share. In Sum of Two Integers (LC 371), the answer is built from both numbers bit by bit, with carries, so no bit can be ignored.

SWE Reasoning

Spot it

The statement asks for the bitwise AND of every integer between two bounds, inclusive.
The range can be as large as 2 billion numbers, so a loop over the range is too slow.
The statement asks for the common leading bits of two numbers, or the longest shared binary prefix.
A small example by hand shows that the answer is always prefix followed by zeros.

The invariant, step by step

Start with shift = 0. left and right are the original ends.
A round runs left >>= 1, right >>= 1 and shift += 1. Now left and right are the original ends with their lowest shift bits removed.
Removing the same number of low bits from both ends keeps their shared prefix. It does not matter which low bits were removed.
The loop stops when left == right. At that moment the value is exactly the shared prefix of the original ends.
Every bit below the prefix is 0 in the AND, because the range contains the number prefix followed by 0111...1 and the number prefix followed by 1000...0.
left << shift puts the prefix back in its original place with shift zeros below it. That is the answer.

Traps

return left without << shift. The result is the prefix without its trailing zeros. For left = 5 and right = 7, it returns 1 instead of 4. For left = 22 and right = 30, it returns 1 instead of 16.
return left & right of the two ends. A number inside the range can have a 0 where both ends have a 1. For left = 22 and right = 30, this returns 22, but the right answer is 16.
Shifting only right. left never changes, so for left > 0 the two values may never become equal. The loop does not end.
Looping over the whole range with result &= value. The answer is right, but the range can hold about 2 billion numbers, so the solution is too slow.

Practice

Canonical LeetCode:Bitwise AND of Numbers Range (LC 201)