Swap All Even and Odd Bits

Problem Statement

Given a non-negative integer n, swap all even-positioned bits with odd-positioned bits in its binary representation.

• Even bits are at positions: 0, 2, 4, …
• Odd bits are at positions: 1, 3, 5, …

Return the number formed after swapping all even and odd bits.

Examples

Example 1:

Input: n =23
Binary: 0001 0111
After swapping: 0010 1011
Output: 43

Example 2:

Input: n = 2
Binary: 0000 0010
After swapping: 0000 0100
Output: 4

Different Approaches

1️⃣ Bit Manipulation

Intuition:

In binary, each bit at even position should be swapped with the bit at the adjacent odd position. We can isolate even and odd bits using bit masking and then shift them accordingly:

• Use a mask to extract even bits: 0xAAAAAAAA (in 32-bit: all odd positions set)
• Use a mask to extract odd bits: 0x55555555 (in 32-bit: all even positions set)

Then:

• Right shift even bits by 1 to bring them to odd positions
• Left shift odd bits by 1 to bring them to even positions
• Combine both using bitwise OR

Code:

#include <iostream>
using namespace std;

int swapEvenOddBits(int n) {
    // Mask all even bits (positions 0, 2, 4...): 0x55555555
    int evenBits = n & 0x55555555;

    // Mask all odd bits (positions 1, 3, 5...): 0xAAAAAAAA
    int oddBits = n & 0xAAAAAAAA;

    // Shift even bits to odd positions
    evenBits <<= 1;

    // Shift odd bits to even positions
    oddBits >>= 1;

    // Combine both
    return (evenBits | oddBits);
}

int main() {
    int n = 23;
    cout << "Original number: " << n << endl;
    cout << "After swapping even and odd bits: " << swapEvenOddBits(n) << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(1)
  • Constant number of operations using bitwise logic.
• Space Complexity:O(1)
  • Only a few integer variables used.