Guide to Competitive Programming

And Operation The and operation x & y produces a number that has one bits in positions where both x and y have one bits.

For example, 22 & 26 = 18, because

10110 (22)
& 11010 (26)
= 10010 (18) .

Using the and operation, we can check if a number x is even because x & 1 = 0 if x is even, and x & 1 = 1 if x is odd. More generally, x is divisible by 2k exactly when x & (2k − 1) = 0.

Or Operation The or operation x | y produces a number that has one bits in positions where at least one of x and y have one bits.

For example, 22 | 26 = 30, because
10110 (22)
| 11010 (26)
= 11110 (30) .

Xor Operation The xor operation x ˆ y produces a number that has one bits in
positions where exactly one of x and y have one bits.

For example, 22 ˆ 26 = 12,
because
10110 (22)
ˆ 11010 (26)
= 01100 (12) .

Not Operation The not operation ~x produces a number where all the bits of x have been inverted. The formula ~x = −x −1 holds, for example, ~29 = −30. The result of the not operation at the bit level depends on the length of the bit representation, because the operation inverts all bits. For example, if the numbers are 32-bit int
numbers, the result is as follows:
x = 29 00000000000000000000000000011101
~x = −30 11111111111111111111111111100010
Bit Shifts The left bit shift x << k appends k zero bits to the number, and the right bit shift x >> k removes the k last bits from the number. For example, 14 << 2 = 56, because 14 and 56 correspond to 1110 and 111000. Similarly, 49 >> 3 = 6, because 49 and 6 correspond to 110001 and 110. Note that x << k corresponds to multiplying x by 2k , and x >> k corresponds to dividing x by 2k rounded down to an integer.

Bit Masks A bit mask of the form 1 << k has a one bit in position k, and all other bits are zero, so we can use such masks to access single bits of numbers. In particular, the kth bit of a number is one exactly when x & (1 << k) is not zero. The following code prints the bit representation of an int number x:

for (int k = 31; k >= 0; k–) {
if (x&(1<<k)) cout << “1”;
else cout << “0”;
}

It is also possible to modify single bits of numbers using similar ideas. The formula x | (1 << k) sets the kth bit of x to one, the formula x & ~(1 << k) sets the kth bit of x to zero, and the formula x ˆ (1 << k) inverts the kth bit of x.

Then, the formula x & (x −1) sets the last one bit of x to zero, and the formula x & −x sets all the one bits to zero, except for the last one bit. The formula x | (x − 1) inverts all the bits after the last one bit. Finally, a positive number x is a power of two exactly when x & (x − 1) = 0.

One pitfall when using bit masks is that 1<<k is always an int bit mask. An easy way to create a long long bit mask is 1LL<<k.

Additional Functions The g++ compiler also provides the following functions for counting bits:
• __builtin_clz(x): the number of zeros at the beginning of the bit representation
• __builtin_ctz(x): the number of zeros at the end of the bit representation
• __builtin_popcount(x): the number of ones in the bit representation
• __builtin_parity(x): the parity (even or odd) of the number of ones in the bit representation
The functions can be used as follows:

int x = 5328; // 00000000000000000001010011010000
cout << __builtin_clz(x) << “\n”; // 19
cout << __builtin_ctz(x) << “\n”; // 4
cout << __builtin_popcount(x) << “\n”; // 5
cout << __builtin_parity(x) << “\n”; // 1
Note that the above functions only support int numbers, but there are also long long versions of the functions available with the suffix ll.