Given an unsigned 32-bit integer n, return an integer where all of n's even bits are swapped with their adjacent odd bits.

Example 1:

Input: n = 41
Output: 22

Example 2:

Input: n = 23
Output: 43

In Plain English

New to this one? Start here. Below is the core idea in everyday language, plus a real-world analogy—then the sections that follow build on it with the formal reasoning, code, and step-by-step walkthroughs.

Intuition

Swapping even and odd bits means that each bit in an even position is swapped with the bit in the next odd position, and vice versa. Note that the positions start at position 0, which is the position of the least significant bit.

The key thing to notice is that, in order to perform the swap:

• All bits in the even positions need to be shifted one position to the left.
• All bits in the odd positions need to be shifted one position to the right.

This suggests that if we had a way to extract all the even and odd-positioned bits separately, we could shift them accordingly and then merge them back together, so the odd-positioned bits are in the even positions, and vice versa.

Let’s start by figuring out how to obtain the even and odd bits of n.

Obtaining all even bits
To obtain all even bits of n, we can use a mask which has all even bit positions set to 1:

Performing a bitwise-AND with this mask and n gives us an integer where all the bits at odd positions are set to 0, ensuring only the bits in even positions of n are preserved:

Obtaining all odd bits
Similarly, to obtain all the odd bits of n, we can use a mask with all odd bit positions are set to 1:

Performing a bitwise-AND with this mask and n gives us an integer where all the bits at even positions are set to 0, ensuring only the bits at odd positions of n are preserved:

Now that we’ve extracted all the even bits and odd bits separately, let’s use them to obtain the result, where the bits at odd and even positions are swapped.

Shifting and merging the bits at odd and even positions
We can use the shift operator to shift the bits at even positions to the left once, and the bits at odd positions to the right once:

Then, to merge these together, we can use the bitwise-OR operator because it combines the two sets of bits into the final result.

Now, the odd-positioned bits are in the even positions and vice versa.

Implementation

def swap_odd_and_even_bits(n: int) -> int:
    even_mask = 0x55555555   # 01010101010101010101010101010101
    odd_mask = 0xAAAAAAAA  # 10101010101010101010101010101010
    even_bits = n & even_mask
    odd_bits = n & odd_mask
    # Shift the even bits to the left, the odd bits to the right, and merge these
    # shifted values together.
    return (even_bits << 1) | (odd_bits >> 1)

// n is an unsigned 32-bit integer; use unsigned shifts (logical, no sign bit).
uint32_t swapOddAndEvenBits(uint32_t n) {
    uint32_t evenMask = 0x55555555u;   // 0101...01: 1s at even positions
    uint32_t oddMask  = 0xAAAAAAAAu;   // 1010...10: 1s at odd positions
    uint32_t evenBits = n & evenMask;
    uint32_t oddBits  = n & oddMask;
    // Even bits move left one slot; odd bits move right one slot; merge with OR.
    return (evenBits << 1) | (oddBits >> 1);
}

// Use the UNSIGNED right shift (>>>) so the sign bit does not leak in.
int swapOddAndEvenBits(int n) {
    int evenMask = 0x55555555;   // 0101...01: 1s at even positions
    int oddMask  = 0xAAAAAAAA;   // 1010...10: 1s at odd positions
    int evenBits = n & evenMask;
    int oddBits  = n & oddMask;
    // Even bits move left one slot; odd bits move right one slot; merge with OR.
    return (evenBits << 1) | (oddBits >>> 1);
}

Complexity Analysis

Time complexity: The time complexity of swap_odd_and_even_bits is $O(1)$.

Space complexity: The space complexity is $O(1)$.

Dry Runs

Two step-by-step walkthroughs of the algorithm below: a valid case (the expected happy path) and an invalid / edge case that exercises the tricky parts. Each step shows the program state as the code runs—the same steps apply to Python, C++ and Java.