Treat n as a 32-bit unsigned integer. Number its bit positions from 0 (least significant) to 31 (most significant): positions 0, 2, 4, …, 30 are the "even" positions, and 1, 3, 5, …, 31 are the "odd" positions.
Swap every adjacent pair of bits — the bit at even position 2k trades places with the bit at odd position 2k + 1, for each k from 0 to 15 — and return the resulting integer.
For example, for n = 23 (binary ...00010111), pairing bits from the low end gives (bit0, bit1) = (1, 1), (bit2, bit3) = (1, 0), (bit4, bit5) = (1, 0). Swapping each pair yields bits 1, 1, 0, 1, 0, 1 (positions 0 through 5), which is 43.
Example
n = 2 has only bit 1 (odd) set; swapping moves it to bit 0, giving 1.
Constraints
- 0 <= n <= 2^32 - 1
Intuition
A first pass walks all 16 adjacent bit-position pairs one at a time: for each pair (2k, 2k + 1), it extracts the even bit and the odd bit individually with a shift-and-mask, then re-inserts them into the result with their positions swapped.
function swapOddEvenBits(n) {
let result = 0;
// Walk all 16 adjacent bit-position pairs: (0,1), (2,3), ..., (30,31).
for (let k = 0; k < 16; k++) {
const evenPos = 2 * k;
const oddPos = evenPos + 1;
// Extract each bit individually by shifting it down to position 0.
const evenBit = (n >>> evenPos) & 1;
const oddBit = (n >>> oddPos) & 1;
// Re-insert them into the result with their positions swapped.
if (evenBit) result |= (1 << oddPos);
if (oddBit) result |= (1 << evenPos);
}
// Unsigned-coerce in case bit 31 ended up set in the result.
return result >>> 0;
}This is still O(1) — a fixed 32-bit word caps the loop at 16 iterations no matter what n is — but each iteration does four separate operations (extract the even bit, extract the odd bit, insert one, insert the other) just to move two bits. That's up to 64 individual bitwise operations to process a single word. Can we do better?
The key observation: swapping bit 0 with bit 1 uses the exact same shift-by-one move as swapping bit 2 with bit 3, bit 4 with bit 5, and every other pair — the loop repeats one identical operation 16 times instead of doing it once across the whole word. AND, OR, and shift all apply to every bit position at once, so instead of handling each pair individually you can mask out all the even-position bits as one group and all the odd-position bits as one other group, shift each group by one in a single operation, and OR the two groups back together. That's this chapter's own shift-and-merge bit reordering technique — isolate two interleaved groups, shift each toward the other's original position, then recombine — turning 16 small per-pair operations into a fixed handful of whole-word ones.
- The signed/unsigned 32-bit trap.
ncan reach2^32 - 1, so bit 31 can be set — but JS's bitwise operators coerce every operand to a signed 32-bit integer first. Once bit 31 is involved, an intermediate likeevenBits << 1or the final OR can come back negative even though the value is meant as unsigned. - The fix:
>>> 0(unsigned right-shift by zero) reinterprets the same 32 bits as unsigned without changing any of them. The stored solution applies it after each mask (evenBits,oddBits), after the left shift (shiftedEven), and on the final OR — skip any one of those and a largencan silently return a negative number instead of the swapped unsigned value.
The stored solution's variable names already match this idea — EVEN_MASK/ODD_MASK isolate the two groups, evenBits/oddBits hold them, shiftedEven/shiftedOdd move them into place — so no bridging is needed.
A single 32-bit integer doesn't have a natural "sequence being scanned" the way an array walkthrough does, and forcing a pointer diagram here would just redraw the pair-by-pair loop we're trying to move past. So instead, here's the mask → shift → OR pipeline traced directly on one worked example. Walking it through:
- n = 182 — binary
0b10110110(bit 7 down to bit 0:1 0 1 1 0 1 1 0). - evenBits = n & EVEN_MASK — keep only the bits at positions 0, 2, 4, 6 and zero out the rest: bits 2 and 4 survive →
0b00010100= 20. - oddBits = n & ODD_MASK — keep only the bits at positions 1, 3, 5, 7: bits 1, 5, and 7 survive →
0b10100010= 162. - shiftedEven = (evenBits << 1) >>> 0 — every even bit slides up into its odd neighbor's slot:
0b00101000= 40. - shiftedOdd = oddBits >>> 1 — every odd bit slides down into its even neighbor's slot:
0b01010001= 81. - result = (shiftedEven | shiftedOdd) >>> 0 — merge the two shifted groups in one OR:
0b01111001= 121.
One pass over the whole word swapped every pair at once — bit 6/7 flips (0,1 → 1,0), bit 4/5 stays put (1,1 → 1,1, a no-op the same way a matched pair is in the brute force), bit 2/3 flips (1,0 → 0,1), bit 0/1 flips (0,1 → 1,0) — with no per-pair branch anywhere in the pipeline.
Optimization
Two masks, shift, and OR
0x55555555 is 0101...0101 in binary — a 1 at every even bit position — so ANDing it with n isolates exactly the even-position bits. 0xAAAAAAAA is its complement, 1010...1010, isolating the odd-position bits. Shifting the even bits left by one moves each into its neighboring odd slot; shifting the odd bits right by one moves each into its neighboring even slot. ORing the two shifted groups back together places every bit in its swapped position.
JavaScript's bitwise operators coerce operands to signed 32-bit integers, so once bit 31 is involved (any n >= 2^31), an intermediate value like evenBits << 1 can come out negative even though we mean it as unsigned. >>> 0 (unsigned right shift by zero) reinterprets those 32 bits as unsigned again without changing any bit, so applying it to the final OR (and to each masked/shifted intermediate) keeps the whole computation in the correct 0 to 2^32 - 1 range.
O(1) time and space — a fixed number of masks, shifts, and an OR regardless of n.
function swapOddEvenBits(n) {
const EVEN_MASK = 0x55555555; // 1 at every even bit position (0, 2, 4, ...)
const ODD_MASK = 0xaaaaaaaa; // 1 at every odd bit position (1, 3, 5, ...)
// Isolate each group, then unsigned-coerce so bit 31 doesn't read as negative.
const evenBits = (n & EVEN_MASK) >>> 0;
const oddBits = (n & ODD_MASK) >>> 0;
// Move even bits up into the odd slots, odd bits down into the even slots.
const shiftedEven = (evenBits << 1) >>> 0;
const shiftedOdd = oddBits >>> 1;
return (shiftedEven | shiftedOdd) >>> 0;
}Complexity analysis
Time complexity: O(1). Here's why:
- Every step — the two ANDs (
n & EVEN_MASK,n & ODD_MASK), the two shifts (evenBits << 1,oddBits >>> 1), the OR, and the>>> 0coercions — touches all 32 bits of a fixed-width word at once, not one bit at a time. - The number of operations doesn't depend on
n's value or how many bits are set — it's the same handful of instructions whethernis 0 or2^32 - 1.
So the whole swap runs in O(1) — a constant number of word-wide operations, instead of the brute force's 16 iterations of per-pair extract-and-insert work.
Space complexity: O(1). Here's why:
- Only a fixed set of intermediates (
evenBits,oddBits,shiftedEven,shiftedOdd) are kept, each a single 32-bit integer. - None of them grow with
n— there's no array, map, or recursion stack.
So the algorithm uses O(1) space, matching the brute force's space bound while doing far less work to get there.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| n = 0 | 0 | Smallest possible input — no bits set, nothing to swap. |
| n = 5 | 10 | Two set bits split across two different pairs, exercising both the even and odd mask groups in one call. |
| n = 12 | 12 | A fixed point below the top of the word — the (bit 2, bit 3) pair is already matched (1, 1), so swapping it is a no-op. |
| n = 2147483649 | 1073741826 | Bit 31 set alongside bit 0 — exercises the signed/unsigned trap at the very top of the word while also touching the bottom pair. |
| n = 2271560481 | 1268417298 | General mixed-nibble value with both matched and swapped pairs throughout the word. |
Try it yourself
Write your solution against the real judge before checking the reference.