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 Kernighan's Bit Trick, which you haven’t finished yet.

P1MediumMental model~2 min speedrun

Bit Reversal with Shifts and Masks (Reverse Bits)

Grows into

Shared Prefix Carry Add Gray Step

The problem

Reverse Bits (LC 190)(opens leetcode.com)

You are given an integer n. Write it as a 32-bit binary number (padding with leading zeros), reverse the order of those 32 bits, and return the number the reversed bits represent.

For example, 2 is 00000000000000000000000000000010; reversed it becomes 01000000000000000000000000000000, which is 1073741824.

Example 1

Input:n = 43261596

Output:964176192

43261596 is 00000010100101000001111010011100 in 32-bit binary. Reversed, that reads 00111001011110000010100101000000, which is 964176192.

Bit Tricks

word ➔ masks + shifts ➔ rearranged word

Spot it when: The statement asks you to rearrange the bits of one fixed-width number: mirror the bits, or flip them with a mask.

Bit Tricks

Python

1	def reverse_bits(n: int) -> int:
2	"""Reverse Bits: mirrors the 32 bits of `n`.
3	Time: O(1) (32 iterations) \| Space: O(1)
4	"""
5	res = 0
6	for _ in range(32):
7	res = (res << 1) \| (n & 1) # Shift result left, append n's lowest bit
8	n >>= 1 # Consume that bit from n
9	return res

Invariant: After k rounds, res holds the lowest k bits of the original n in reverse order, and n holds the bits not read yet.

Treat the number as a fixed row of 32 bits and move bits with shifts and masks, never by converting it to a string. reverse_bits peels the lowest bit off n with n & 1 and appends it to res with res << 1. Each round shifts every bit already in res one place up and drops n's next-lowest bit into the free slot, so after 32 rounds bit i of n sits at bit 31 - i of res. The trap is stopping when n reaches 0: n = 2 would return 1 instead of 1073741824, because the 30 leading zeros of n were never shifted in.

See it run

Reverse Bits, step by step

round 0n 22res 0

The top row is n and the bottom row is res. Each column is one bit position, with the highest position on the left.

read the lowest bit of n, read with n & 1
written the lowest bit of res, just set by the round
next the bit that n >>= 1 moves into the lowest place

Start: n = 22 is 00010110 in 8 bits, and res = 0.

res

1 / 19

Gotchas1 of 4

The trap
Gotcha 1: Stopping when n reaches 0 with while n:
Mistake
```
while n:
```
Fix
```
for _ in range(32):
```
What happens: Python ints have no fixed width, so the loop must count the 32 bits itself. while n: stops when the last 1 bit of n is read. The leading zeros of n are then never shifted into res. Each of them should move res one place to the left.
Example: n = 2
Mistake: returns 1Fix: returns 1073741824
Gotcha 2: Shifting res after adding the bit
Mistake
```
res = (res | (n & 1)) << 1
```
Fix
```
res = (res << 1) | (n & 1)
```
What happens: Each round must first make room at bit 0, then put the new bit there. Shifting after adding moves every bit one place too far. After 32 rounds, res is twice the right answer, so it can need 33 bits.
Example: n = 1
Mistake: returns 4294967296Fix: returns 2147483648
Gotcha 3: Appending n instead of its lowest bit n & 1
Mistake
```
res = (res << 1) | n
```
Fix
```
res = (res << 1) | (n & 1)
```
What happens: res must receive one bit per round. (res << 1) | n puts every remaining bit of n into res at once. The bits of n then land in the wrong places, several times over.
Example: n = 2
Mistake: returns 5368709120Fix: returns 1073741824
Gotcha 4: Not shifting n right after each round
Mistake
```
res = (res << 1) | (n & 1)
```
Fix
```
res = (res << 1) | (n & 1)
n >>= 1
```
What happens: n & 1 always reads bit 0 of n. n >>= 1 moves the next bit of n into bit 0 for the next round. Without it, every round reads the same bit, and res gets 32 copies of it.
Example: n = 2
Mistake: returns 0Fix: returns 1073741824

Not this one if…

You only count or test set bits, as in Counting Bits (LC 338); no bit has to change position. See Kernighan's Bit Trick

Deep Dive

Why the loop reverses the bits

A 32-bit number has bit positions 0 to 31. Position 0 is the lowest bit, and position 31 is the highest bit. Reversing means that the bit at position i ends at position 31 - i.

Each round of reverse_bits does two things. res = (res << 1) | (n & 1) moves every bit already in res one position up, and it writes the lowest bit of n into position 0 of res. Then n >>= 1 removes that bit from n.

Bit i of the original n is read in round i + 1. After it enters res at position 0, it is shifted up in each of the remaining 31 - i rounds. So it finishes at position 31 - i. This is exactly the card's invariant: after k rounds, res holds the lowest k bits of the original n in reverse order.

Example with 8 bits for readability: n = 00010110. After round 1, res = 00000000 and the bit read was 0. After round 4, res = 00000110. After round 8, res = 01101000, which is n written backwards.

Why the loop must run exactly 32 times

A Python int has no fixed width. The loop must supply the width, because the number itself does not.

Leading zeros of n are real bits in the 32-bit view. In the reversed number they become low bits, so each one must shift res once. For n = 2, bit 1 is set and the other 31 bits are zero. The right answer is 1073741824, which is 2 to the power 30.

while n: stops after n becomes 0. For n = 2, that is after two rounds, and res is 1. The 30 leading zeros were never shifted in. Counting rounds with for _ in range(32) fixes this.

The same loop works with another width. For a 16-bit task, use range(16). The width is the only value that changes.

The cost: rounds times work per round

The loop runs 32 times. Each round does one shift, one AND, one OR and one shift. That is a constant amount of work, so the time is O(1) for a fixed width. In general it is O(W) for a word of W bits.

The space is O(1). The function keeps only res, n and the loop counter.

If the function is called many times, there is a faster method. It swaps the two 16-bit halves, then the 8-bit groups, then 4, 2 and 1, with masks such as 0xF0F0F0F0. That takes 5 steps instead of 32 rounds, and it returns the same result. I compared both methods on 20,000 random 32-bit numbers, and they matched.

Start with the loop. It is short and easy to check. Mention the mask method as an optimisation.

Flipping the bits with a mask: Number Complement (LC 476)

The card also covers a second way to rearrange the bits of one number: flip every bit with a mask. Complement of Base 10 Integer (LC 1009) and Number Complement (LC 476) ask for this. The complement keeps the same bit length and turns every 0 into 1 and every 1 into 0.

Build a mask of n.bit_length() ones with mask = (1 << n.bit_length()) - 1. Then n ^ mask flips exactly those bits, because XOR with 1 flips a bit. For n = 5 the bits are 101, the mask is 111, and the answer is 010, which is 2.

The width here is not 32. It is the bit length of n, because the leading zeros of a 32-bit view must stay zeros. The fixed-width mask n ^ 0xFFFFFFFF would also flip them, and 5 ^ 0xFFFFFFFF gives 4294967290, not 2.

One edge case: Complement of Base 10 Integer (LC 1009) allows n = 0, and its answer is 1, because 0 is written as the single bit 0. The mask formula gives 0 for n = 0, so return 1 for that input.

Reverse Bits moves each bit to a new position and keeps its value. The complement keeps each position and changes its value. Both use shifts or masks on the binary form, and neither converts the number to decimal arithmetic.

60-Second Pitch

"I treat the input as a fixed row of 32 bits and move bits with shifts and masks, so I do not convert it to a string. In each round I shift res left by one, and I append the lowest bit of n with n & 1. Then I shift n right by one. After 32 rounds, bit i of the input is at bit 31 - i of res. I run exactly 32 rounds, because stopping when n is 0 would lose the leading zeros. That is O(1) time and O(1) space for a fixed width. If the function is called many times, I can swap the halves, then the groups of 8, 4, 2 and 1 bits with masks. That takes 5 steps and gives the same answer."

Common Questions

What is the time and space complexity of reverse_bits?: O(1) time and O(1) space for a 32-bit input. The loop runs 32 times, and each round does a constant amount of work. For a word of W bits, the time is O(W).
Why does the loop not stop when n becomes 0?: Leading zeros of n are bits too. After reversal they sit at the low end of res, and each one needs a shift. For n = 2, stopping early returns 1 instead of 1073741824. The loop counts the 32 positions with range(32).
How do you make it faster if the function is called many times?: Swap the 16-bit halves, then the 8-bit groups, then 4, 2 and 1, using masks such as 0xF0F0F0F0 and 0xCCCCCCCC. That takes 5 steps. Another option is a lookup table with the reversal of every byte, and then you combine 4 lookups.
How would you handle this in a language with fixed-width integers?: Use an unsigned 32-bit type, or in Java use >>> so the sign bit is not copied during the right shift. The result of reversing a number with bit 0 set has bit 31 set. A signed integer would show it as negative, although the bits are the same.
How would you flip the bits of a number, as in Number Complement (LC 476)?: Use n ^ ((1 << n.bit_length()) - 1). The mask has one 1 for every bit up to the highest set bit, and XOR with 1 flips a bit. For n = 5 the answer is 2. Do not use a 32-bit mask, because it would also flip the leading zeros. For Complement of Base 10 Integer (LC 1009), return 1 when n is 0.

SWE Reasoning

Spot it

The statement says reverse, mirror or flip the bits of a fixed-width number.
The statement asks for the complement of a number: flip every bit, but only the bits up to the highest set bit.
The width is named: 32 bits, 16 bits, a byte. The width decides how many rounds you run.
The answer depends on the position of each bit, not only on how many bits are set. That separates this card from counting set bits, as in Counting Bits (LC 338).
A string conversion such as bin(n) would work, but the interviewer wants constant extra space or a bit-level solution.

The invariant, step by step

Start with res = 0. After 0 rounds, res holds 0 bits, which is correct.
In a round, res << 1 moves every bit already in res one position up. Position 0 is now free.
n & 1 is the lowest bit of n. | (n & 1) writes it into position 0 of res.
n >>= 1 removes that bit from n. The next bit of n is now at position 0.
After k rounds, res holds the lowest k bits of the original n. The first bit read is the highest of those in res, so they are in reverse order.
After 32 rounds, all 32 bits are in res. Bit i of n is at position 31 - i, so res is the reversed number.

Traps

while n: instead of for _ in range(32). The loop stops when n is 0, so leading zeros are never shifted in. reverse_bits(2) returns 1 instead of 1073741824.
Shifting after adding. res = (res | (n & 1)) << 1 shifts the new bit too. After 32 rounds the result is twice the right value. reverse_bits(1) returns 4294967296 instead of 2147483648.
Adding n instead of n & 1. (res << 1) | n puts all remaining bits of n into res in one round. reverse_bits(2) returns 5368709120 instead of 1073741824.
Forgetting n >>= 1. n & 1 reads the same bit in every round. For n = 2 the result is 0 instead of 1073741824.
Using a signed view. The task is about an unsigned 32-bit value. The result of reverse_bits(1) is 2147483648, which does not fit in a signed 32-bit integer. In Java or C++, use an unsigned type, or the >>> operator in Java.

Practice

Canonical LeetCode:Reverse Bits (LC 190)Complement of Base 10 Integer (LC 1009)Number Complement (LC 476)

Theory Context•Bit Manipulation

Builds on Kernighan's Bit Trick, which you haven’t finished yet.

P1MediumMental model~2 min speedrun

Bit Reversal with Shifts and Masks (Reverse Bits)

Grows into

Shared Prefix Carry Add Gray Step

The problem

Reverse Bits (LC 190)(opens leetcode.com)

You are given an integer n. Write it as a 32-bit binary number (padding with leading zeros), reverse the order of those 32 bits, and return the number the reversed bits represent.

For example, 2 is 00000000000000000000000000000010; reversed it becomes 01000000000000000000000000000000, which is 1073741824.

Example 1

Input:n = 43261596

Output:964176192

43261596 is 00000010100101000001111010011100 in 32-bit binary. Reversed, that reads 00111001011110000010100101000000, which is 964176192.

Bit Tricks

word ➔ masks + shifts ➔ rearranged word

Spot it when: The statement asks you to rearrange the bits of one fixed-width number: mirror the bits, or flip them with a mask.

Bit Tricks

Python

1	def reverse_bits(n: int) -> int:
2	"""Reverse Bits: mirrors the 32 bits of `n`.
3	Time: O(1) (32 iterations) \| Space: O(1)
4	"""
5	res = 0
6	for _ in range(32):
7	res = (res << 1) \| (n & 1) # Shift result left, append n's lowest bit
8	n >>= 1 # Consume that bit from n
9	return res

Invariant: After k rounds, res holds the lowest k bits of the original n in reverse order, and n holds the bits not read yet.

See it run

Reverse Bits, step by step

round 0n 22res 0

The top row is n and the bottom row is res. Each column is one bit position, with the highest position on the left.

read the lowest bit of n, read with n & 1
written the lowest bit of res, just set by the round
next the bit that n >>= 1 moves into the lowest place

Start: n = 22 is 00010110 in 8 bits, and res = 0.

res

1 / 19

Gotchas1 of 4

The trap
Gotcha 1: Stopping when n reaches 0 with while n:
Mistake
```
while n:
```
Fix
```
for _ in range(32):
```
What happens: Python ints have no fixed width, so the loop must count the 32 bits itself. while n: stops when the last 1 bit of n is read. The leading zeros of n are then never shifted into res. Each of them should move res one place to the left.
Example: n = 2
Mistake: returns 1Fix: returns 1073741824
Gotcha 2: Shifting res after adding the bit
Mistake
```
res = (res | (n & 1)) << 1
```
Fix
```
res = (res << 1) | (n & 1)
```
What happens: Each round must first make room at bit 0, then put the new bit there. Shifting after adding moves every bit one place too far. After 32 rounds, res is twice the right answer, so it can need 33 bits.
Example: n = 1
Mistake: returns 4294967296Fix: returns 2147483648
Gotcha 3: Appending n instead of its lowest bit n & 1
Mistake
```
res = (res << 1) | n
```
Fix
```
res = (res << 1) | (n & 1)
```
What happens: res must receive one bit per round. (res << 1) | n puts every remaining bit of n into res at once. The bits of n then land in the wrong places, several times over.
Example: n = 2
Mistake: returns 5368709120Fix: returns 1073741824
Gotcha 4: Not shifting n right after each round
Mistake
```
res = (res << 1) | (n & 1)
```
Fix
```
res = (res << 1) | (n & 1)
n >>= 1
```
What happens: n & 1 always reads bit 0 of n. n >>= 1 moves the next bit of n into bit 0 for the next round. Without it, every round reads the same bit, and res gets 32 copies of it.
Example: n = 2
Mistake: returns 0Fix: returns 1073741824

Not this one if…

You only count or test set bits, as in Counting Bits (LC 338); no bit has to change position. See Kernighan's Bit Trick

Deep Dive

Why the loop reverses the bits

A 32-bit number has bit positions 0 to 31. Position 0 is the lowest bit, and position 31 is the highest bit. Reversing means that the bit at position i ends at position 31 - i.

Why the loop must run exactly 32 times

A Python int has no fixed width. The loop must supply the width, because the number itself does not.

while n: stops after n becomes 0. For n = 2, that is after two rounds, and res is 1. The 30 leading zeros were never shifted in. Counting rounds with for _ in range(32) fixes this.

The same loop works with another width. For a 16-bit task, use range(16). The width is the only value that changes.

The cost: rounds times work per round

The space is O(1). The function keeps only res, n and the loop counter.

Start with the loop. It is short and easy to check. Mention the mask method as an optimisation.

Flipping the bits with a mask: Number Complement (LC 476)

60-Second Pitch

Common Questions

What is the time and space complexity of reverse_bits?: O(1) time and O(1) space for a 32-bit input. The loop runs 32 times, and each round does a constant amount of work. For a word of W bits, the time is O(W).
Why does the loop not stop when n becomes 0?: Leading zeros of n are bits too. After reversal they sit at the low end of res, and each one needs a shift. For n = 2, stopping early returns 1 instead of 1073741824. The loop counts the 32 positions with range(32).
How do you make it faster if the function is called many times?: Swap the 16-bit halves, then the 8-bit groups, then 4, 2 and 1, using masks such as 0xF0F0F0F0 and 0xCCCCCCCC. That takes 5 steps. Another option is a lookup table with the reversal of every byte, and then you combine 4 lookups.
How would you handle this in a language with fixed-width integers?: Use an unsigned 32-bit type, or in Java use >>> so the sign bit is not copied during the right shift. The result of reversing a number with bit 0 set has bit 31 set. A signed integer would show it as negative, although the bits are the same.
How would you flip the bits of a number, as in Number Complement (LC 476)?: Use n ^ ((1 << n.bit_length()) - 1). The mask has one 1 for every bit up to the highest set bit, and XOR with 1 flips a bit. For n = 5 the answer is 2. Do not use a 32-bit mask, because it would also flip the leading zeros. For Complement of Base 10 Integer (LC 1009), return 1 when n is 0.

SWE Reasoning

Spot it

The statement says reverse, mirror or flip the bits of a fixed-width number.
The statement asks for the complement of a number: flip every bit, but only the bits up to the highest set bit.
The width is named: 32 bits, 16 bits, a byte. The width decides how many rounds you run.
The answer depends on the position of each bit, not only on how many bits are set. That separates this card from counting set bits, as in Counting Bits (LC 338).
A string conversion such as bin(n) would work, but the interviewer wants constant extra space or a bit-level solution.

The invariant, step by step

Start with res = 0. After 0 rounds, res holds 0 bits, which is correct.
In a round, res << 1 moves every bit already in res one position up. Position 0 is now free.
n & 1 is the lowest bit of n. | (n & 1) writes it into position 0 of res.
n >>= 1 removes that bit from n. The next bit of n is now at position 0.
After k rounds, res holds the lowest k bits of the original n. The first bit read is the highest of those in res, so they are in reverse order.
After 32 rounds, all 32 bits are in res. Bit i of n is at position 31 - i, so res is the reversed number.

Traps

while n: instead of for _ in range(32). The loop stops when n is 0, so leading zeros are never shifted in. reverse_bits(2) returns 1 instead of 1073741824.
Shifting after adding. res = (res | (n & 1)) << 1 shifts the new bit too. After 32 rounds the result is twice the right value. reverse_bits(1) returns 4294967296 instead of 2147483648.
Adding n instead of n & 1. (res << 1) | n puts all remaining bits of n into res in one round. reverse_bits(2) returns 5368709120 instead of 1073741824.
Forgetting n >>= 1. n & 1 reads the same bit in every round. For n = 2 the result is 0 instead of 1073741824.
Using a signed view. The task is about an unsigned 32-bit value. The result of reverse_bits(1) is 2147483648, which does not fit in a signed 32-bit integer. In Java or C++, use an unsigned type, or the >>> operator in Java.

Practice

Canonical LeetCode:Reverse Bits (LC 190)Complement of Base 10 Integer (LC 1009)Number Complement (LC 476)

Theory Context•Bit Manipulation

Builds on Kernighan's Bit Trick, which you haven’t finished yet.

P1MediumMental model~2 min speedrun

Bit Reversal with Shifts and Masks (Reverse Bits)

Grows into

Shared Prefix Carry Add Gray Step

The problem

Reverse Bits (LC 190)(opens leetcode.com)

You are given an integer n. Write it as a 32-bit binary number (padding with leading zeros), reverse the order of those 32 bits, and return the number the reversed bits represent.

For example, 2 is 00000000000000000000000000000010; reversed it becomes 01000000000000000000000000000000, which is 1073741824.

Example 1

Input:n = 43261596

Output:964176192

43261596 is 00000010100101000001111010011100 in 32-bit binary. Reversed, that reads 00111001011110000010100101000000, which is 964176192.

Bit Tricks

word ➔ masks + shifts ➔ rearranged word

Spot it when: The statement asks you to rearrange the bits of one fixed-width number: mirror the bits, or flip them with a mask.

Bit Tricks

Python

1	def reverse_bits(n: int) -> int:
2	"""Reverse Bits: mirrors the 32 bits of `n`.
3	Time: O(1) (32 iterations) \| Space: O(1)
4	"""
5	res = 0
6	for _ in range(32):
7	res = (res << 1) \| (n & 1) # Shift result left, append n's lowest bit
8	n >>= 1 # Consume that bit from n
9	return res

Invariant: After k rounds, res holds the lowest k bits of the original n in reverse order, and n holds the bits not read yet.

See it run

Reverse Bits, step by step

round 0n 22res 0

The top row is n and the bottom row is res. Each column is one bit position, with the highest position on the left.

read the lowest bit of n, read with n & 1
written the lowest bit of res, just set by the round
next the bit that n >>= 1 moves into the lowest place

Start: n = 22 is 00010110 in 8 bits, and res = 0.

res

1 / 19

Gotchas1 of 4

The trap
Gotcha 1: Stopping when n reaches 0 with while n:
Mistake
```
while n:
```
Fix
```
for _ in range(32):
```
What happens: Python ints have no fixed width, so the loop must count the 32 bits itself. while n: stops when the last 1 bit of n is read. The leading zeros of n are then never shifted into res. Each of them should move res one place to the left.
Example: n = 2
Mistake: returns 1Fix: returns 1073741824
Gotcha 2: Shifting res after adding the bit
Mistake
```
res = (res | (n & 1)) << 1
```
Fix
```
res = (res << 1) | (n & 1)
```
What happens: Each round must first make room at bit 0, then put the new bit there. Shifting after adding moves every bit one place too far. After 32 rounds, res is twice the right answer, so it can need 33 bits.
Example: n = 1
Mistake: returns 4294967296Fix: returns 2147483648
Gotcha 3: Appending n instead of its lowest bit n & 1
Mistake
```
res = (res << 1) | n
```
Fix
```
res = (res << 1) | (n & 1)
```
What happens: res must receive one bit per round. (res << 1) | n puts every remaining bit of n into res at once. The bits of n then land in the wrong places, several times over.
Example: n = 2
Mistake: returns 5368709120Fix: returns 1073741824
Gotcha 4: Not shifting n right after each round
Mistake
```
res = (res << 1) | (n & 1)
```
Fix
```
res = (res << 1) | (n & 1)
n >>= 1
```
What happens: n & 1 always reads bit 0 of n. n >>= 1 moves the next bit of n into bit 0 for the next round. Without it, every round reads the same bit, and res gets 32 copies of it.
Example: n = 2
Mistake: returns 0Fix: returns 1073741824

Not this one if…

You only count or test set bits, as in Counting Bits (LC 338); no bit has to change position. See Kernighan's Bit Trick

Deep Dive

Why the loop reverses the bits

A 32-bit number has bit positions 0 to 31. Position 0 is the lowest bit, and position 31 is the highest bit. Reversing means that the bit at position i ends at position 31 - i.

Why the loop must run exactly 32 times

A Python int has no fixed width. The loop must supply the width, because the number itself does not.

while n: stops after n becomes 0. For n = 2, that is after two rounds, and res is 1. The 30 leading zeros were never shifted in. Counting rounds with for _ in range(32) fixes this.

The same loop works with another width. For a 16-bit task, use range(16). The width is the only value that changes.

The cost: rounds times work per round

The space is O(1). The function keeps only res, n and the loop counter.

Start with the loop. It is short and easy to check. Mention the mask method as an optimisation.

Flipping the bits with a mask: Number Complement (LC 476)

60-Second Pitch

Common Questions

What is the time and space complexity of reverse_bits?: O(1) time and O(1) space for a 32-bit input. The loop runs 32 times, and each round does a constant amount of work. For a word of W bits, the time is O(W).
Why does the loop not stop when n becomes 0?: Leading zeros of n are bits too. After reversal they sit at the low end of res, and each one needs a shift. For n = 2, stopping early returns 1 instead of 1073741824. The loop counts the 32 positions with range(32).
How do you make it faster if the function is called many times?: Swap the 16-bit halves, then the 8-bit groups, then 4, 2 and 1, using masks such as 0xF0F0F0F0 and 0xCCCCCCCC. That takes 5 steps. Another option is a lookup table with the reversal of every byte, and then you combine 4 lookups.
How would you handle this in a language with fixed-width integers?: Use an unsigned 32-bit type, or in Java use >>> so the sign bit is not copied during the right shift. The result of reversing a number with bit 0 set has bit 31 set. A signed integer would show it as negative, although the bits are the same.
How would you flip the bits of a number, as in Number Complement (LC 476)?: Use n ^ ((1 << n.bit_length()) - 1). The mask has one 1 for every bit up to the highest set bit, and XOR with 1 flips a bit. For n = 5 the answer is 2. Do not use a 32-bit mask, because it would also flip the leading zeros. For Complement of Base 10 Integer (LC 1009), return 1 when n is 0.

SWE Reasoning

Spot it

The statement says reverse, mirror or flip the bits of a fixed-width number.
The statement asks for the complement of a number: flip every bit, but only the bits up to the highest set bit.
The width is named: 32 bits, 16 bits, a byte. The width decides how many rounds you run.
The answer depends on the position of each bit, not only on how many bits are set. That separates this card from counting set bits, as in Counting Bits (LC 338).
A string conversion such as bin(n) would work, but the interviewer wants constant extra space or a bit-level solution.

The invariant, step by step

Start with res = 0. After 0 rounds, res holds 0 bits, which is correct.
In a round, res << 1 moves every bit already in res one position up. Position 0 is now free.
n & 1 is the lowest bit of n. | (n & 1) writes it into position 0 of res.
n >>= 1 removes that bit from n. The next bit of n is now at position 0.
After k rounds, res holds the lowest k bits of the original n. The first bit read is the highest of those in res, so they are in reverse order.
After 32 rounds, all 32 bits are in res. Bit i of n is at position 31 - i, so res is the reversed number.

Traps

while n: instead of for _ in range(32). The loop stops when n is 0, so leading zeros are never shifted in. reverse_bits(2) returns 1 instead of 1073741824.
Shifting after adding. res = (res | (n & 1)) << 1 shifts the new bit too. After 32 rounds the result is twice the right value. reverse_bits(1) returns 4294967296 instead of 2147483648.
Adding n instead of n & 1. (res << 1) | n puts all remaining bits of n into res in one round. reverse_bits(2) returns 5368709120 instead of 1073741824.
Forgetting n >>= 1. n & 1 reads the same bit in every round. For n = 2 the result is 0 instead of 1073741824.
Using a signed view. The task is about an unsigned 32-bit value. The result of reverse_bits(1) is 2147483648, which does not fit in a signed 32-bit integer. In Java or C++, use an unsigned type, or the >>> operator in Java.

Practice

Canonical LeetCode:Reverse Bits (LC 190)Complement of Base 10 Integer (LC 1009)Number Complement (LC 476)

Theory Context•Bit Manipulation

Builds on Kernighan's Bit Trick, which you haven’t finished yet.

P1MediumMental model~2 min speedrun

Bit Reversal with Shifts and Masks (Reverse Bits)

Grows into

Shared Prefix Carry Add Gray Step

The problem

Reverse Bits (LC 190)(opens leetcode.com)

You are given an integer n. Write it as a 32-bit binary number (padding with leading zeros), reverse the order of those 32 bits, and return the number the reversed bits represent.

For example, 2 is 00000000000000000000000000000010; reversed it becomes 01000000000000000000000000000000, which is 1073741824.

Example 1

Input:n = 43261596

Output:964176192

43261596 is 00000010100101000001111010011100 in 32-bit binary. Reversed, that reads 00111001011110000010100101000000, which is 964176192.

Bit Tricks

word ➔ masks + shifts ➔ rearranged word

Spot it when: The statement asks you to rearrange the bits of one fixed-width number: mirror the bits, or flip them with a mask.

Bit Tricks

Python

1	def reverse_bits(n: int) -> int:
2	"""Reverse Bits: mirrors the 32 bits of `n`.
3	Time: O(1) (32 iterations) \| Space: O(1)
4	"""
5	res = 0
6	for _ in range(32):
7	res = (res << 1) \| (n & 1) # Shift result left, append n's lowest bit
8	n >>= 1 # Consume that bit from n
9	return res

Invariant: After k rounds, res holds the lowest k bits of the original n in reverse order, and n holds the bits not read yet.

See it run

Reverse Bits, step by step

round 0n 22res 0

The top row is n and the bottom row is res. Each column is one bit position, with the highest position on the left.

read the lowest bit of n, read with n & 1
written the lowest bit of res, just set by the round
next the bit that n >>= 1 moves into the lowest place

Start: n = 22 is 00010110 in 8 bits, and res = 0.

res

1 / 19

Gotchas1 of 4

The trap
Gotcha 1: Stopping when n reaches 0 with while n:
Mistake
```
while n:
```
Fix
```
for _ in range(32):
```
What happens: Python ints have no fixed width, so the loop must count the 32 bits itself. while n: stops when the last 1 bit of n is read. The leading zeros of n are then never shifted into res. Each of them should move res one place to the left.
Example: n = 2
Mistake: returns 1Fix: returns 1073741824
Gotcha 2: Shifting res after adding the bit
Mistake
```
res = (res | (n & 1)) << 1
```
Fix
```
res = (res << 1) | (n & 1)
```
What happens: Each round must first make room at bit 0, then put the new bit there. Shifting after adding moves every bit one place too far. After 32 rounds, res is twice the right answer, so it can need 33 bits.
Example: n = 1
Mistake: returns 4294967296Fix: returns 2147483648
Gotcha 3: Appending n instead of its lowest bit n & 1
Mistake
```
res = (res << 1) | n
```
Fix
```
res = (res << 1) | (n & 1)
```
What happens: res must receive one bit per round. (res << 1) | n puts every remaining bit of n into res at once. The bits of n then land in the wrong places, several times over.
Example: n = 2
Mistake: returns 5368709120Fix: returns 1073741824
Gotcha 4: Not shifting n right after each round
Mistake
```
res = (res << 1) | (n & 1)
```
Fix
```
res = (res << 1) | (n & 1)
n >>= 1
```
What happens: n & 1 always reads bit 0 of n. n >>= 1 moves the next bit of n into bit 0 for the next round. Without it, every round reads the same bit, and res gets 32 copies of it.
Example: n = 2
Mistake: returns 0Fix: returns 1073741824

Not this one if…

You only count or test set bits, as in Counting Bits (LC 338); no bit has to change position. See Kernighan's Bit Trick

Deep Dive

Why the loop reverses the bits

A 32-bit number has bit positions 0 to 31. Position 0 is the lowest bit, and position 31 is the highest bit. Reversing means that the bit at position i ends at position 31 - i.

Why the loop must run exactly 32 times

A Python int has no fixed width. The loop must supply the width, because the number itself does not.

while n: stops after n becomes 0. For n = 2, that is after two rounds, and res is 1. The 30 leading zeros were never shifted in. Counting rounds with for _ in range(32) fixes this.

The same loop works with another width. For a 16-bit task, use range(16). The width is the only value that changes.

The cost: rounds times work per round

The space is O(1). The function keeps only res, n and the loop counter.

Start with the loop. It is short and easy to check. Mention the mask method as an optimisation.

Flipping the bits with a mask: Number Complement (LC 476)

60-Second Pitch

Common Questions

What is the time and space complexity of reverse_bits?: O(1) time and O(1) space for a 32-bit input. The loop runs 32 times, and each round does a constant amount of work. For a word of W bits, the time is O(W).
Why does the loop not stop when n becomes 0?: Leading zeros of n are bits too. After reversal they sit at the low end of res, and each one needs a shift. For n = 2, stopping early returns 1 instead of 1073741824. The loop counts the 32 positions with range(32).
How do you make it faster if the function is called many times?: Swap the 16-bit halves, then the 8-bit groups, then 4, 2 and 1, using masks such as 0xF0F0F0F0 and 0xCCCCCCCC. That takes 5 steps. Another option is a lookup table with the reversal of every byte, and then you combine 4 lookups.
How would you handle this in a language with fixed-width integers?: Use an unsigned 32-bit type, or in Java use >>> so the sign bit is not copied during the right shift. The result of reversing a number with bit 0 set has bit 31 set. A signed integer would show it as negative, although the bits are the same.
How would you flip the bits of a number, as in Number Complement (LC 476)?: Use n ^ ((1 << n.bit_length()) - 1). The mask has one 1 for every bit up to the highest set bit, and XOR with 1 flips a bit. For n = 5 the answer is 2. Do not use a 32-bit mask, because it would also flip the leading zeros. For Complement of Base 10 Integer (LC 1009), return 1 when n is 0.

SWE Reasoning

Spot it

The statement says reverse, mirror or flip the bits of a fixed-width number.
The statement asks for the complement of a number: flip every bit, but only the bits up to the highest set bit.
The width is named: 32 bits, 16 bits, a byte. The width decides how many rounds you run.
The answer depends on the position of each bit, not only on how many bits are set. That separates this card from counting set bits, as in Counting Bits (LC 338).
A string conversion such as bin(n) would work, but the interviewer wants constant extra space or a bit-level solution.

The invariant, step by step

Start with res = 0. After 0 rounds, res holds 0 bits, which is correct.
In a round, res << 1 moves every bit already in res one position up. Position 0 is now free.
n & 1 is the lowest bit of n. | (n & 1) writes it into position 0 of res.
n >>= 1 removes that bit from n. The next bit of n is now at position 0.
After k rounds, res holds the lowest k bits of the original n. The first bit read is the highest of those in res, so they are in reverse order.
After 32 rounds, all 32 bits are in res. Bit i of n is at position 31 - i, so res is the reversed number.

Traps

while n: instead of for _ in range(32). The loop stops when n is 0, so leading zeros are never shifted in. reverse_bits(2) returns 1 instead of 1073741824.
Shifting after adding. res = (res | (n & 1)) << 1 shifts the new bit too. After 32 rounds the result is twice the right value. reverse_bits(1) returns 4294967296 instead of 2147483648.
Adding n instead of n & 1. (res << 1) | n puts all remaining bits of n into res in one round. reverse_bits(2) returns 5368709120 instead of 1073741824.
Forgetting n >>= 1. n & 1 reads the same bit in every round. For n = 2 the result is 0 instead of 1073741824.
Using a signed view. The task is about an unsigned 32-bit value. The result of reverse_bits(1) is 2147483648, which does not fit in a signed 32-bit integer. In Java or C++, use an unsigned type, or the >>> operator in Java.

Practice

Canonical LeetCode:Reverse Bits (LC 190)Complement of Base 10 Integer (LC 1009)Number Complement (LC 476)