C++ Programming

Chapter 8: Bit Manipulation

Units of information

A bit is the smallest unit of data, with a value of either 0 or 1. The bit can be used to indicate which of two options is selected (true/false, yes/no, on/off, et c.).

A byte consists of 8 bits, and it is the basic unit of data in programming. One byte can store an integer between 0 and 255.

Binary numbers

The usual way of presenting numbers is to use base 10, with numbers from 0 to 9. However, the computer uses it internally the base 2 (or binary) system, where the only numbers are 0 and 1 (bits).

In a binary number, the 1-bit indicates which powers of 2 are included. For example, in the binary number 100101, bits 0, 2 and 5 (reading from the right) are set to 1, so this is equivalent to the base-10 number: 2⁰ + 2² + 2⁵ = 1 + 4 + 32 = 37.

When k bits are available, they can generate 2^k different combinations. It follows that k bits can be used stores 2^k different values.

Bits in programming

In C++, a numeric value of type int is usually 32-bit, consisting of four bytes. The minimum value is –2³¹ and the maximum value is 2³¹-1.

For example, if the int variable has a value of 37, it is stored like this:

00000000 00000000 00000000 00100101

In a computer, the first bit of a number tells its sign. If the bit is 0, the number is positive (or zero), and if bit is 1, the number is negative. A negative number is stored as two's complement, where x becomes -x by first changing all its bits to the opposite of they are and then adding 1 to the result.

For example, if the int variable has a value of -37, it is stored like this:

11111111 11111111 11111111 11011011

In C++, a numeric value can be either signed or unsigned. By default, a numeric value has a sign, so you can store both positive and negative numbers. However, if the numeric value is unsigned, its positive range is doubled.

For example, the following code creates an unsigned int-variable:

unsigned int x;

In this case, the lowest possible value is 0 and the maximum value is 2³²-1.

Bit operations

The a & b (and) operation generates a number, with 1 bits at all positions in which both a and b have a 1 bit. For example, 26 & 19 is 18:

    11010 = 26
    10011 = 19
--------------
  & 10010 = 18

The operation a | b (or) forms a number, with a 1 bit at all positions where either in a or b (or both) there is a 1 bit. For example, 26 | 19 is 27:

    11010 = 26
    10011 = 19
--------------
  | 11011 = 27

The operation a ^ b (xor) generates a number, with a 1 bit at all positions where a and b have different bits. For example, 26 ^ 19 is 9:

    11010 = 26
    10011 = 19
--------------
  ^ 01001 =  9

The following code snippet illustrates bit operations:

int a = 26, b = 19;
cout << (a&b) << "\n"; // 18
cout << (a|b) << "\n"; // 27
cout << (a^b) << "\n"; // 9

Flipping (ones-complementing) bits

The ~x operation changes each bit in x to its opposite (0s become 1s and 1s become 0s). The interpretation of this operation depends on the number of bytes in the number and the sign.

For example, if 37 is of type int, the operation works as follows:

00000000 00000000 00000000 00100101 = 37
11111111 11111111 11111111 11011010 = ~37 = -38

The complement value ~x is equal to -x-1.

Bit shifting and masking

The operation x<<k moves x's bits k to the left, adding zeros at the end. This is equivalent to multiplying by 2^k. For example, 5<<2 is 20 and 101<<2 in bits is 10100.

The operation x>>k moves x's bits k to the right removing bits at the end. This is equivalent to dividing by 2^k (rounding down). For example, 22>>2 is 5 and 10110>>2 in bits is 101.

Often handy is the bit mask 1<<k, where bit k is a 1 bit and there are 0s in all other positions. For example, we can print x bitwise like this:

int x = 37;
for (int k = 31; k >= 0; k--) {
    if (x&(1<<k)) cout << "1";
    else cout << "0";
}
cout << "\n";

The program prints out the following:

00000000000000000000000000100101

Tie koodariksi