How to Exchange the Odd and Even Bits of a 32-bit Integer?

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).

Example1:
Input: num = 2（0b10）
Output 1 (0b01)

Example2:
Input: num = 3
Output: 3

Note:
0 <= num <= pow(2, 30) – 1
The result integer fits into 32-bit integer.

Simulation Algorithm to Exchange Bits

We can simulate the process, exchanging the odd/even bits of an integer.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int exchangeBits(int num) {
        int ret = 0;
        for (int i = 0; i <= 30; i += 2){
            int a1 = (num & (1 << i));
            int b1 = (num & (1 << (i+1)));
            if (a1) ret += (1 << (i+1));
            if (b1) ret += (1 << i);
        }
        return ret;
    }
};

class Solution {
public:
    int exchangeBits(int num) {
        int ret = 0;
        for (int i = 0; i <= 30; i += 2){
            int a1 = (num & (1 << i));
            int b1 = (num & (1 << (i+1)));
            if (a1) ret += (1 << (i+1));
            if (b1) ret += (1 << i);
        }
        return ret;
    }
};

Using std::C++ bitset to Exchange Bits

In C++, the bitset can be thought as a bit array, then we can exchange the odd and even bits.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int exchangeBits(int num) {
        bitset<32> bitNum(num);
        for (int i = 0; i < 16; i++) {
            int t = bitNum[i + i];
            bitNum[i + i] = bitNum[2 * i + 1];
            bitNum[2 * i + 1] = t;
        }
        return (int)bitNum.to_ulong();
    }
};

class Solution {
public:
    int exchangeBits(int num) {
        bitset<32> bitNum(num);
        for (int i = 0; i < 16; i++) {
            int t = bitNum[i + i];
            bitNum[i + i] = bitNum[2 * i + 1];
            bitNum[2 * i + 1] = t;
        }
        return (int)bitNum.to_ulong();
    }
};

Bit Swapping by Bit Tweaks

Let’s see the following values:

0x55555555 = 0b0101_0101_0101_0101_0101_0101_0101_0101
0xaaaaaaaa = 0b1010_1010_1010_1010_1010_1010_1010_1010

Then, we can obtain the odd bits as a value A, and obtain the even bits as a value B, then perform a bit shifting on both, then do the OR operation.

1
2
3
4
5
6
7
8
9

class Solution {
    public int exchangeBits(int num) {
        int odd = num & 0x55555555;
        int even = num & 0xaaaaaaaa;
        odd = odd << 1;
        even = even >> 1;
        return odd | even;
    }
}

class Solution {
    public int exchangeBits(int num) {
        int odd = num & 0x55555555;
        int even = num & 0xaaaaaaaa;
        odd = odd << 1;
        even = even >> 1;
        return odd | even;
    }
}

All algorithms take O(1) constant time and O(1) constant space.

–EOF (The Ultimate Computing & Technology Blog) —