Cracking The Coding Interview Together – Problem 5.7: Pairwise Swap

Imagine you are profiling a high-throughput network engine or a real-time graphics pipeline. Every microsecond counts, and your CPU profiler points directly to a utility function that processes pixel channels or packet headers. You notice a loop that iterates over bits, swapping adjacent pairs. It looks harmless, but under heavy load, those branch mispredictions and loop overheads are quietly choking your application's throughput.

As senior engineers, we know that writing clean code isn't just about making it readable; it's about understanding how our code translates to bare metal. Today, we are going to tackle a classic bit manipulation puzzle: Pairwise Swap. Our goal is to swap the odd and even bits of an integer using as few CPU instructions as possible. No loops, no conditional branches—just pure, elegant bitwise arithmetic. Let's dive in and master this low-level optimization together.

Problem Statement

The problem asks us to write a program to swap odd and even bits in an integer with as few instructions as possible. Specifically, bit 0 and bit 1 should be swapped, bit 2 and bit 3 should be swapped, and so on, all the way through the width of the integer.

For example, if we are given a 32-bit integer represented in binary:

Input:  10101010 10101010 10101010 10101010
Output: 01010101 01010101 01010101 01010101

Our operational goal is to achieve this transformation in $O(1)$ time complexity, utilizing a minimal instruction set that can execute in a handful of CPU clock cycles.

Analyze the Problem Together

Let's break down the constraints and find our "Aha!" moment. If we approach this naively, we might think about iterating through the integer from bit 0 to bit 31, extracting each pair of bits, swapping them using temporary variables, and placing them back into a new integer.

Why is this naive approach a bad idea? First, a loop running 16 times (for 16 pairs in a 32-bit integer) introduces loop control overhead. Second, extracting and shifting bits individually requires multiple operations per pair, leading to dozens of instructions. In a performance-critical system, this is unacceptable.

Instead, let's think about how we can perform this operation in parallel across the entire integer. What if we could isolate all the even bits at once, isolate all the odd bits at once, shift them simultaneously, and then merge them back together?

This is where bitmasking comes to the rescue. Let's look at the binary representation of a 32-bit integer. We want to separate:

• Even bits: Positions 0, 2, 4, 6, 8, ...
• Odd bits: Positions 1, 3, 5, 7, 9, ...

To isolate these bits, we need two masks:

• A mask with 1s at all even positions: 01010101... in binary. In hexadecimal, 5 is 0101. So, a 32-bit mask of alternating 0s and 1s is 0x55555555.
• A mask with 1s at all odd positions: 10101010... in binary. In hexadecimal, A is 1010. So, a 32-bit mask of alternating 1s and 0s is 0xAAAAAAAA.

Let's compare the naive approach with our proposed bitmasking approach:

Questions for the Interviewer

Before we write a single line of code, let's demonstrate our senior engineering mindset by asking clarifying questions. This ensures we don't make incorrect assumptions about the environment or data types:

• "Are we assuming a standard 32-bit integer, or should this solution scale to 64-bit integers?" (This determines whether we use 0x55555555 or 0x5555555555555555L as our masks).
• "How should we handle signed vs. unsigned integers?" (In Java, integers are signed. When shifting odd bits to the right, we must use the logical right shift >>> instead of the arithmetic right shift >> to prevent sign extension from filling the leftmost bits with 1s).
• "Are there any language-specific constraints or performance targets we should keep in mind?" (This shows we care about the execution environment and compiler optimizations).

Think About the Solution

Let's design the high-level architecture of our solution. The algorithm can be broken down into three simple, elegant steps:

1. Isolate and Shift Even Bits: Mask the input integer with 0x55555555 to keep only the even bits. Shift these bits left by 1 position so they move into the odd positions.
2. Isolate and Shift Odd Bits: Mask the input integer with 0xAAAAAAAA to keep only the odd bits. Shift these bits right by 1 position so they move into the even positions.
3. Combine: Merge the two shifted values using a bitwise OR (|) operator.

Let's trace this with a simple 8-bit example to build intuition. Suppose our input is 10110110 (which is 182 in decimal):

• Even mask (0x55 or 01010101): 10110110 & 01010101 = 00010100. Shift left by 1: 00101000.
• Odd mask (0xAA or 10101010): 10110110 & 10101010 = 10100010. Shift right by 1: 01010001.
• Combine with OR: 00101000 | 01010001 = 01111001.

Look at that! The adjacent pairs have been perfectly swapped. Let's write the code to implement this.

Write Code and Explain

Here is the production-ready Java implementation. Note the use of the logical right shift operator (>>>) to handle signed integers correctly.

public class PairwiseSwap {

    /**
     * Swaps odd and even bits in a 32-bit integer.
     * 
     * @param x the input integer
     * @return the integer with swapped odd and even bits
     */
    public static int swapBits(int x) {
        // Mask to isolate even bits: 0101 0101 0101 0101 0101 0101 0101 0101
        int evenMask = 0x55555555;
        
        // Mask to isolate odd bits:  1010 1010 1010 1010 1010 1010 1010 1010
        int oddMask = 0xAAAAAAAA;

        // Extract even bits and shift them left to odd positions
        int shiftedEven = (x & evenMask) << 1;

        // Extract odd bits and shift them right to even positions.
        // We use the logical right shift (>>>) to ensure 0s are filled on the left,
        // preventing sign extension issues with negative numbers.
        int shiftedOdd = (x & oddMask) >>> 1;

        // Combine the shifted bits using bitwise OR
        return shiftedEven | shiftedOdd;
    }

    public static void main(String[] args) {
        int input = 0b10110110; // 182 in decimal
        int result = swapBits(input);
        
        System.out.println("Input (Binary):  " + Integer.toBinaryString(input));
        System.out.println("Result (Binary): " + Integer.toBinaryString(result));
    }
}

Step-by-Step Walkthrough

Let's walk through the execution of this code:

1. We define our masks as hexadecimal constants. 0x55555555 and 0xAAAAAAAA are highly optimized constants that the compiler can load directly into registers.
2. The expression (x & evenMask) << 1 clears all odd bits, leaving only the even bits intact, and then shifts them one position to the left. This moves every even bit to its adjacent odd position.
3. The expression (x & oddMask) >>> 1 clears all even bits, leaving only the odd bits intact, and then shifts them one position to the right. Crucially, >>> ensures that if the most significant bit (the sign bit in Java) was set, we don't accidentally propagate 1s into our shifted result.
4. Finally, we merge the two intermediate results using the bitwise OR (|) operator. Since the shifted even bits only occupy odd positions, and the shifted odd bits only occupy even positions, the OR operation safely combines them without any interference.

Time & Space Complexity

Let's analyze the efficiency of our solution:

• Time Complexity: O(1). The number of operations is entirely constant and does not depend on the value of the input. We perform exactly 2 bitwise ANDs, 2 shifts, and 1 bitwise OR. This translates to a mere 5 CPU instructions, executing in a fraction of a nanosecond.
• Space Complexity: O(1). We do not allocate any dynamic memory or data structures. The operations are performed directly within CPU registers.

Why This Problem Matters (The Senior Perspective)

You might ask: "When will I ever need to swap odd and even bits in a real-world enterprise application?" While the specific task of swapping adjacent bits is rare in standard web development, the underlying patterns are foundational to high-performance software engineering.

Consider these real-world scenarios:

• Network Protocols & Serialization: When parsing custom binary protocols or working with systems like Protobuf or FlatBuffers, you often need to pack and unpack fields at the bit level to save bandwidth.
• Graphics & Image Processing: Swapping color channels (e.g., converting ARGB to RGBA) or manipulating pixel layouts relies heavily on parallel bitmasking and shifting.
• Cryptography: Many symmetric encryption algorithms (like AES or DES) rely on permutations and bit-shuffling networks. Implementing these using bitwise masks is the key to achieving cryptographic-grade performance.
• Thread Safety & Lock-Free Programming: Bitwise operations are inherently atomic at the hardware level when performed on register-sized variables. Understanding how to pack multiple state variables into a single 64-bit integer allows you to build lock-free, concurrent data structures using atomic Compare-And-Swap (CAS) operations.

Final Thoughts

We've taken a problem that could easily have been solved with a slow, clunky loop and turned it into a masterclass in low-level optimization. By leveraging bitwise masks and shifts, we reduced the execution time to a constant 5 instructions.

As an exercise to stretch your mind: How would you modify this algorithm to swap groups of 2 bits (e.g., swapping bits 0-1 with bits 2-3)? What about groups of 4 bits? (Hint: Think about how your hexadecimal masks would change!).

Thanks for reading, and happy coding! We'll see you in the next deep dive on The Dev Learnings.