Bits and pieces

Bit-wise operations:

• And (&), Or (|), Xor (^), Not (~)
• Shifting (<<, >>)

Exchange

How can you switch the values of two (integer) variables without using an auxiliary third one?

Finding the non-duplicate

You are given an array of integers all of which repeat twice with the exception of one. Can you find the value of that element using linear time and constant memory?

Power of 2

How can you check whether a positive integer is a power of 2 without using loops or the logarithm function?

Counting ones

Given an integer, count the number of ones in its binary presentation.

Gray code

Consider the following list of all four values of two bits.

0	0
0	1
1	1
1	0

Note that each following line is formed from the previous one by changing only one bit (marked in bold). Such a sequence is called a Gray code. For example, the following is a Gray code of length 3.

0	0	0
0	0	1
0	1	1
0	1	0
1	1	0
1	1	1
1	0	1
1	0	0

How can we construct a Gray code of arbitrary length $n \geq 1$?