Swap Odd and Even Bits
Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, and so on).
Worked Examples
n = 23 (00010111₂)43 (00101011₂)⚖️Formal Constraints & Bounds
0 <= n <= 232 - 1
Core Insight
0xAAAAAAAA (10101010...) isolates all odd bits; right-shifting moves them to even positions. 0x55555555 (01010101...) isolates all even bits; left-shifting moves them to odd positions. Combining with OR ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1) solves the problem in O(1) instructions.
Real-World Scenario & Production Applications
Hardware bit interleaving/de-interleaving in radio communications, raster display pixel packing, cryptographic permutation S-box operations.
Step-by-Step Execution Trace Table
| Step | Operation | Bitmask Used | Effect on Bits | Binary Transformation Example (n = 23 = 00010111_2) |
|---|---|---|---|---|
| 1 | Extract Even Bits | 0xAAAAAAAA | Clears all odd positions | 00010111 & 10101010 = 00000010_2 |
| 2 | Shift Even Bits Right | >> 1 | Moves even bits to odd positions | 00000010 >> 1 = 00000001_2 |
| 3 | Extract Odd Bits | 0x55555555 | Clears all even positions | 00010111 & 01010101 = 00010101_2 |
| 4 | Shift Odd Bits Left | << 1 | Moves odd bits to even positions | 00010101 << 1 = 00101010_2 |
| 5 | Combine Results | Bitwise OR \vert | Merges odd and even swapped halves | 00000001 \vert 00101010 = 00101011_2 (43) |
| 1 | even_mask, odd_mask = 0xAAAAAAAA, 0x55555555 |
| 2 | return ((n & even_mask) >> 1) | ((n & odd_mask) << 1) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Two hex constants swapping bits in one line looks unreadable until you picture what each mask is physically doing.
🧦 The Analogy: Two Combs Pulling Apart a Zipper
Your bits alternate like a zipper: even-position, odd-position, even-position, odd-position... You can't swap neighbors in place directly, so instead you pull the zipper apart into two separate combs, then reassemble it flipped.
🔑 Why It Works
- Trick 1 — Comb A (
n & 0xAAAAAAAA): This mask has1s at every even bit position, so ANDing with it keeps only those bits and zeroes everything else — it's a comb that grabs every other tooth. - Trick 2 — Comb B (
n & 0x55555555): The complementary mask, grabbing exactly the interleaved teeth Comb A left behind. - Trick 3 — Sliding into place (
>> 1/<< 1): Shift Comb A's teeth one slot right and Comb B's teeth one slot left — each comb now sits exactly where the other one used to be. - Trick 4 — Zipping back up (
|): Since the two combs never overlap (each owns a disjoint set of bit positions), OR-ing them together zips the row back into one number, now with every neighbor pair swapped.
Using wrong 32-bit bitmasks: The even bitmask must be
0xAAAAAAAA(bits at positions 1, 3, 5...) and odd bitmask0x55555555(bits at positions 0, 2, 4...). Using transposed or 16-bit masks truncates high bits.Shifting in the wrong direction: Even bits must shift right (
>> 1) to land on odd positions, and odd bits must shift left (<< 1) to land on even positions.Operator precedence without grouping: In
(n & 0xAAAAAAAA) >> 1 | (n & 0x55555555) << 1, ensure parenthesis grouping around shifts and bitwise ANDs before bitwise OR.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Swap bits at even and odd index positions, pairwise bit transposition, constant instruction count.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: 0xAAAAAAAA (1010...) isolates all bits at odd positions; 0x55555555 (0101...) isolates all bits at even positions.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Sign-extension on odd-bit right shift: Shifting
(n & 0xAAAAAAAA)right by 1 using signed>>can propagate the sign bit if the 31st bit is set. Use logical shift>>>or mask with0x7FFFFFFF.Hex mask typos:
0xAAAAis only 16 bits; a 32-bit integer requires 8 hex digits (0xAAAAAAAAand0x55555555).Iterating bit-by-bit: Looping 16 times with swaps is needlessly slow when two bitwise masks accomplish the swap in 3 CPU cycles.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I isolate all odd bits using the mask
0xAAAAAAAAand shift them right by 1 into even positions. Concurrently, I isolate all even bits using0x55555555and shift them left by 1 into odd positions. Finally, I combine the two shifted values using bitwise OR. Runs inO(1)constant time with zero extra space.
Complexity & Mathematical Proof
O(1)
Look at the execution steps: Masks even bits with 0xAAAAAAAA and shifts right by 1; masks odd bits with 0x55555555 and shifts left by 1; combines with bitwise OR: ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1). Runs in 3 CPU instructions.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1). Single 32-bit integer in CPU register.
Derivation Progression
(n \& 0xAAAAAAAA) >> 1
Extracts all even-positioned bits and shifts them to odd positions.
(n \& 0x55555555) << 1
Extracts all odd-positioned bits and shifts them to even positions.
even | odd
Combines swapped bits in single constant-time OR instruction.
Variable Definitions
Fixed 32-bit word width (3 constant CPU register operations)
Memory Architecture & Bounds
O(1)
O(1) CPU register
O(1) 32-bit integer
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
The problem asks to "swap odd and even bits in an integer with as few operations as possible." Bit 0 and Bit 1 swap, Bit 2 and Bit 3 swap, etc. Iterating bit-by-bit is slow and unnecessary. The structural trigger is SIMD-style Whole-Word Masking: we isolate all even bits with an even-bit mask, isolate all odd bits with an odd-bit mask, shift each into their complementary positions, and recombine with bitwise OR.
Input is a 32-bit integer. The even mask for bits 0, 2, 4... is 0x55555555 (...01010101). The odd mask for bits 1, 3, 5... is 0xAAAAAAAA (...10101010). Time complexity must be strictly using zero loops.
In typed languages, shifting signed negative numbers right with >> propagates sign bits; an unsigned right shift >>> or casting to unsigned integer is necessary. In Python, large integers must be masked with 0xFFFFFFFF to simulate 32-bit unsigned boundaries.
Swap Odd and Even Bits
Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, and so on).
Worked Examples
n = 23 (00010111₂)43 (00101011₂)⚖️Formal Constraints & Bounds
0 <= n <= 232 - 1
Core Insight
0xAAAAAAAA (10101010...) isolates all odd bits; right-shifting moves them to even positions. 0x55555555 (01010101...) isolates all even bits; left-shifting moves them to odd positions. Combining with OR ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1) solves the problem in O(1) instructions.
Real-World Scenario & Production Applications
Hardware bit interleaving/de-interleaving in radio communications, raster display pixel packing, cryptographic permutation S-box operations.
Step-by-Step Execution Trace Table
| Step | Operation | Bitmask Used | Effect on Bits | Binary Transformation Example (n = 23 = 00010111_2) |
|---|---|---|---|---|
| 1 | Extract Even Bits | 0xAAAAAAAA | Clears all odd positions | 00010111 & 10101010 = 00000010_2 |
| 2 | Shift Even Bits Right | >> 1 | Moves even bits to odd positions | 00000010 >> 1 = 00000001_2 |
| 3 | Extract Odd Bits | 0x55555555 | Clears all even positions | 00010111 & 01010101 = 00010101_2 |
| 4 | Shift Odd Bits Left | << 1 | Moves odd bits to even positions | 00010101 << 1 = 00101010_2 |
| 5 | Combine Results | Bitwise OR \vert | Merges odd and even swapped halves | 00000001 \vert 00101010 = 00101011_2 (43) |
| 1 | even_mask, odd_mask = 0xAAAAAAAA, 0x55555555 |
| 2 | return ((n & even_mask) >> 1) | ((n & odd_mask) << 1) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Two hex constants swapping bits in one line looks unreadable until you picture what each mask is physically doing.
🧦 The Analogy: Two Combs Pulling Apart a Zipper
Your bits alternate like a zipper: even-position, odd-position, even-position, odd-position... You can't swap neighbors in place directly, so instead you pull the zipper apart into two separate combs, then reassemble it flipped.
🔑 Why It Works
- Trick 1 — Comb A (
n & 0xAAAAAAAA): This mask has1s at every even bit position, so ANDing with it keeps only those bits and zeroes everything else — it's a comb that grabs every other tooth. - Trick 2 — Comb B (
n & 0x55555555): The complementary mask, grabbing exactly the interleaved teeth Comb A left behind. - Trick 3 — Sliding into place (
>> 1/<< 1): Shift Comb A's teeth one slot right and Comb B's teeth one slot left — each comb now sits exactly where the other one used to be. - Trick 4 — Zipping back up (
|): Since the two combs never overlap (each owns a disjoint set of bit positions), OR-ing them together zips the row back into one number, now with every neighbor pair swapped.
Using wrong 32-bit bitmasks: The even bitmask must be
0xAAAAAAAA(bits at positions 1, 3, 5...) and odd bitmask0x55555555(bits at positions 0, 2, 4...). Using transposed or 16-bit masks truncates high bits.Shifting in the wrong direction: Even bits must shift right (
>> 1) to land on odd positions, and odd bits must shift left (<< 1) to land on even positions.Operator precedence without grouping: In
(n & 0xAAAAAAAA) >> 1 | (n & 0x55555555) << 1, ensure parenthesis grouping around shifts and bitwise ANDs before bitwise OR.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Swap bits at even and odd index positions, pairwise bit transposition, constant instruction count.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: 0xAAAAAAAA (1010...) isolates all bits at odd positions; 0x55555555 (0101...) isolates all bits at even positions.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Sign-extension on odd-bit right shift: Shifting
(n & 0xAAAAAAAA)right by 1 using signed>>can propagate the sign bit if the 31st bit is set. Use logical shift>>>or mask with0x7FFFFFFF.Hex mask typos:
0xAAAAis only 16 bits; a 32-bit integer requires 8 hex digits (0xAAAAAAAAand0x55555555).Iterating bit-by-bit: Looping 16 times with swaps is needlessly slow when two bitwise masks accomplish the swap in 3 CPU cycles.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I isolate all odd bits using the mask
0xAAAAAAAAand shift them right by 1 into even positions. Concurrently, I isolate all even bits using0x55555555and shift them left by 1 into odd positions. Finally, I combine the two shifted values using bitwise OR. Runs inO(1)constant time with zero extra space.
Complexity & Mathematical Proof
O(1)
Look at the execution steps: Masks even bits with 0xAAAAAAAA and shifts right by 1; masks odd bits with 0x55555555 and shifts left by 1; combines with bitwise OR: ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1). Runs in 3 CPU instructions.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1). Single 32-bit integer in CPU register.
Derivation Progression
(n \& 0xAAAAAAAA) >> 1
Extracts all even-positioned bits and shifts them to odd positions.
(n \& 0x55555555) << 1
Extracts all odd-positioned bits and shifts them to even positions.
even | odd
Combines swapped bits in single constant-time OR instruction.
Variable Definitions
Fixed 32-bit word width (3 constant CPU register operations)
Memory Architecture & Bounds
O(1)
O(1) CPU register
O(1) 32-bit integer
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
The problem asks to "swap odd and even bits in an integer with as few operations as possible." Bit 0 and Bit 1 swap, Bit 2 and Bit 3 swap, etc. Iterating bit-by-bit is slow and unnecessary. The structural trigger is SIMD-style Whole-Word Masking: we isolate all even bits with an even-bit mask, isolate all odd bits with an odd-bit mask, shift each into their complementary positions, and recombine with bitwise OR.
Input is a 32-bit integer. The even mask for bits 0, 2, 4... is 0x55555555 (...01010101). The odd mask for bits 1, 3, 5... is 0xAAAAAAAA (...10101010). Time complexity must be strictly using zero loops.
In typed languages, shifting signed negative numbers right with >> propagates sign bits; an unsigned right shift >>> or casting to unsigned integer is necessary. In Python, large integers must be masked with 0xFFFFFFFF to simulate 32-bit unsigned boundaries.