Questions about hexadecimal

Question

Write a program to swap odd and even bits in an integer. For exp, bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped.

The solution uses 0xaaaaaaaa and 0x55555555. Can I know what does 0xaaaaaaaa and 0x55555555 means in binary number?

Answer 1

Each four bits constitutes a hex digit thus:

0000 0    1000 8
0001 1    1001 9
0010 2    1010 A
0011 3    1011 B
0100 4    1100 C
0101 5    1101 D
0110 6    1110 E
0111 7    1111 F

So, for example, 0x1234 would be 0001 0010 0011 01002.

For your specific examples:

0xaaaaaaaa = 1010 1010 ... 1010
0x55555555 = 0101 0101 ... 0101

---

The reason why a solution might use those two values is that, if you AND a value with 0xaaaaaaaa, you'll get only the odd bits (counting from the left), which you can then shift right to move them to the even bit positions.

Similarly, if you AND a value with 0x55555555, you'll get only the even bits, which you can then shift left to move them to the odd bit positions.

Then you can just OR those two values together and the bits have been swapped.

For example, let's start with the 16-bit value abcdefghijklmnop (each letter being a bit and with a zero bit being . to make it more readable):

      abcdefghijklmnop          abcdefghijklmnop
  AND 1.1.1.1.1.1.1.1.      AND .1.1.1.1.1.1.1.1
    = a.c.e.g.i.k.m.o.        = .b.d.f.h.j.l.n.p
>>1 = .a.c.e.g.i.k.m.o    <<1 = b.d.f.h.j.l.n.p.
      \___________                  ___________/
                  \                /
                   .a.c.e.g.i.k.m.o
                OR b.d.f.h.j.l.n.p.
                 = badcfehgjilknmpo

So each group of two bits has been swapped around. In C, that would be something like:

val = ((val & 0xAAAAAAAA) >> 1) | ((val & 0x55555555) << 1);

but, if this is classwork of some description, I'd suggest you work it out yourself by doing individual operations.

For an in-depth explanation of the bitwise operators that allow you to do this, see this excellent answer here.