Guide to Competitive Programming

In programming, an n-bit integer is internally stored as a binary number that consists of n bits. For example, the C++ type int is a 32-bit type, which means that every int number consists of 32 bits. For example, the bit representation of the int number 43 is 00000000000000000000000000101011.

The bits in the representation are indexed from right to left. To convert a bit representation bk . . . b2b1b0 into a number, the formula bk2k +· · ·+b222 + b121 + b020.
can be used. For example,
1 · 25 + 1 · 23 + 1 · 21 + 1 · 20 = 43.

The bit representation of a number is either signed or unsigned. Usually a signed representation is used, which means that both negative and positive numbers can be represented. A signed variable of n bits can contain any integer between −2n−1 and 2n−1 − 1. For example, the int type in C++ is a signed type, so an int variable can contain any integer between −231 and 231 − 1.

The first bit in a signed representation is the sign of the number (0 for nonnegative numbers and 1 for negative numbers), and the remaining n − 1 bits contain the magnitude of the number. Two’s complement is used, which means that the opposite number of a number is calculated by first inverting all the bits in the number and then increasing the number by one. For example, the bit representation of the int number −43 is 11111111111111111111111111010101.

In an unsigned representation, only nonnegative numbers can be used, but the upper bound for the values is larger. An unsigned variable of n bits can contain any integer between 0 and 2n − 1. For example, in C++, an unsigned int variable can contain any integer between 0 and 232 − 1.

There is a connection between the representations: a signed number −x equals an unsigned number 2n − x.

For example, the following code shows that the signed number x = −43 equals the unsigned number y = 232 − 43:

int x = -43;
unsigned int y = x;
cout << x << “\n”; // -43
cout << y << “\n”; // 4294967253

 

If a number is larger than the upper bound of the bit representation, the number will overflow. In a signed representation, the next number after 2n−1 − 1 is −2n−1,

and in an unsigned representation, the next number after 2n − 1 is 0. For example,
consider the following code:

int x = 2147483647
cout << x << “\n”; // 2147483647
x++;
cout << x << “\n”; // -2147483648

Initially, the value of x is 231 − 1. This is the largest value that can be stored in
an int variable, so the next number after 231 − 1 is −231.