Skip to content

05.07. Exchange

Description

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:

  1. 0 <= num <= 2^30 - 1
  2. The result integer fits into 32-bit integer.

Solutions

Solution 1: Bit Manipulation

Thinking

Adjacent odd/even bits must be swapped. Sixteen pairwise swaps work but loop.

All even bits and all odd bits can be gathered with masks and shifted as two blocks.

AND with \(0x55555555\) and shift left; AND with \(0xAAAAAAAA\) and shift right; OR the two halves. A few operations, no loop.

We can perform a bitwise AND operation between num and 0x55555555 to get the even bits of num, and then shift them one bit to the left. Then, we perform a bitwise AND operation between num and 0xaaaaaaaa to get the odd bits of num, and then shift them one bit to the right. Finally, we perform a bitwise OR operation on the two results to get the answer.

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

1
2
3
class Solution:
    def exchangeBits(self, num: int) -> int:
        return ((num & 0x55555555) << 1) | ((num & 0xAAAAAAAA) >> 1)

1
2
3
4
5
class Solution {
    public int exchangeBits(int num) {
        return ((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa)) >> 1;
    }
}

1
2
3
4
5
6
class Solution {
public:
    int exchangeBits(int num) {
        return ((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa)) >> 1;
    }
};

1
2
3
func exchangeBits(num int) int {
    return ((num & 0x55555555) << 1) | (num&0xaaaaaaaa)>>1
}

1
2
3
function exchangeBits(num: number): number {
    return ((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >>> 1);
}

1
2
3
4
5
6
impl Solution {
    pub fn exchange_bits(num: i32) -> i32 {
        let num = num as u32;
        (((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >> 1)) as i32
    }
}

1
2
3
4
5
6
7
8
9
class Solution {
    func exchangeBits(_ num: Int) -> Int {
        let oddShifted = (num & 0x55555555) << 1

        let evenShifted = (num & 0xaaaaaaaa) >> 1

        return oddShifted | evenShifted
    }
}

Comments