//by dnalwqer 04/19/2015
//idea: use an bit number to track whether it is an odd bit or even bit.


public class Solution {
	public int reverseBits(int A) {
		int bit = 0;
		int res = 0;

		while (A != 0) {
			int num = A & 1;
			A = A >>> 1;
			if (num == 1) {
				if (bit % 2 == 0) {
					res |= 1 << (bit + 1);
				}
				else {
					res |= 1 << (bit - 1);
				}
			}
			bit++;
		}
		return res;
	}

	// I have learnt a new method
	// use 0x55555555 to reset all the odd bits to 0 and shift left to get all the right odd numbers, vice verse.

	public int reverseBits2(int A) {
		return ((0x55555555 & A) << 1) | ((0xAAAAAAAA) & A) >> 1);
	}

	public static void main(String []args) {
		Solution s = new Solution();
		int A = Integer.parseInt("011110", 2);
		int res = s.reverseBits(A);
		System.out.println(Integer.toBinaryString(res));
	}
}