Bit Representation
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.
Here is the bit representation of the int number 43:
00000000000000000000000000101011
The bits in the representation are indexed from right to left. To convert a bit
representation bk...b2b1b0 into a number, we can use the formula
bk2k +...+b222+b121 + b020.
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
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
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.