Swap odd and even bits in an 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, etc).

My initial thoughts:
I was thinking to shift the number to the left and then manipulate the bits somehow, shift the number to the right and also do the trick, then combine these two together. But I never figured out the details…

Solution:

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

The solution’s idea is similar to mine… well, to some degree.

  1. Mask the odd bits (keep the odd bits and turn off all the even bits). We can do this by: number & 10101010…. In a 32-bit machine, the mask is 0xAAAAAAAA. After doing that, we have all the odd bits, we shift the number to the right for one position, that puts all the odd bits to the oven position.
  2. Mask the even bits (keep the even bits and turn off all the odd bits). We can do this by: number & 01010101…. In a 32-bit machine, the mask is 0x55555555. After doing that, we have all the even bits, we shift the number to the left for one position, that puts all the even bits to the odd position.
  3. We then | the two results combine them together and output the final number.

We should learn the general way of swapping any two bits in position i and position j.

	public static int swapTwoPositions(int number, int i, int j) {
		return (((number & (1 << i)) >> i) << j)
				| (((number & (1 << j)) >> j) << i)
				| ((~(1 << i)) & (~(1 << j)) & number);
	}

There are three parts separated by |. The first part mask the i position and move it to j position. The second part mask the j position and move it to i position. The third part turns off bits i and j but keep the rest.

Advertisements

1 Comment (+add yours?)

  1. Suriya
    Oct 25, 2012 @ 17:10:13

    Nice one, Very clear and precise explanation!

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: