Problem

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

Input : An integer x Output : An integer y, which odd and even bit swapped (with 0th bit being least significant bit)

Examples

Example 1:

Input: x = 10 = 1010
Output: 5 = 0101
(0th bit and 1st bit have been swapped,also 2nd and 3rd bit have been swapped)

Example 2:

Input: x = 14 (= 1110)
Output: 13 (   = 1101)

Solution

Method 1 - Right shift and left shift with simple masks

Consider an 8-bit unsigned integer:

  • The binary value 10101010 should become 01010101.
  • The binary value 11100010 should become 11010001.

For each bit pair (even and odd bits), we shift the even bits to the right and the odd bits to the left, then combine these shifted bits to form the new number.

Here’s how it works:

  1. Mask even bits and shift them right.
    • 0b10101010 is the mask to isolate even bits.
    • 0b01010101 is the mask to isolate odd bits.
  2. Mask odd bits and shift them left.
    • >> 1 shifts even bits right.
    • << 1 shifts odd bits left.
  3. Combine the results using bitwise OR.

Code

Java
public class Solution {

    public static int swapBits(int n) {
        // Mask even bits
        int evenBits = n & 0b10101010;
        // Mask odd bits
        int oddBits = n & 0b01010101;

        // Shift even bits to the right
        evenBits >>= 1;
        // Shift odd bits to the left
        oddBits <<= 1;

        // Combine the bits
        return evenBits | oddBits;
    }
}
Python
def swap_bits(n):
	return ((n & 0b10101010) >> 1) | ((n & 0b01010101) << 1)

Method 2 - Right shift even bits and left shift odd bits with masks 0xAAAAAAAA & 0x55555555

If we take a closer look at the example, we can observe that we basically need to right shift (>>) all even bits by 1 so that they become odd bits, and left shift (<<) all odd bits by 1 so that they become even bits. The following solution is based on this observation. The solution assumes that input number is stored using 32 bits. Let the input number be x

  1. Get all even bits of x by doing bitwise and of x with 0xAAAAAAAA. The number 0xAAAAAAAA is a 32 bit number with all even bits set as 1 and all odd bits as 0.
  2. Get all odd bits of x by doing bitwise and of x with 0x55555555. The number 0x55555555 is a 32 bit number with all odd bits set as 1 and all even bits as 0.
  3. Right shift all even bits.
  4. Left shift all odd bits.
  5. Combine new even and odd bits and return.

Code

C
unsigned int swapBits(unsigned int x)
{
 // Get all even bits of x
 unsigned int even_bits = x & 0xAAAAAAAA;

 // Get all odd bits of x
 unsigned int odd_bits  = x & 0×55555555;

 even_bits >>= 1; // Right shift even bits
 odd_bits <<= 1; // Left shift odd bits

 return (even_bits | odd_bits); // Combine even and odd bits
}

Note that we have not used normal int, but unsigned it. Because bitwise operators will not work in expected way on signed integer, as we have to take care of additional rules about MSB. In simple words, when a signed integer is shifted right, the MSB isn’t necessarily zero, it’s copied from the old MSB value.

Java
public int swapOddEvenBits(int x) {
	return (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555)<< 1));
}