Monday, March 24, 2014

Swap odd and even bits in an integer

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)

Example
Input  1:  10 = 1010
Output 1:  5  = 0101

(0th bit and 1st bit have been swapped,also 2nd and 3rd bit have been swapped) 

Input  2:  14 = 1110
Output 2:  13 = 1101

Solution

Method 1 - Right shift even bits and left shift odd bits
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.

Here is the c code
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.

Here is code in java
public static int swapOddEvenBits(int x) {
    return (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
}

References  - 
geeksforgeeks
stackoverflow
tian runhe,

Thanks.

Reactions:

0 comments:

Post a Comment