Bits and the math library

Summary

To the processor, an integer is a row of bits, and C++ offers operators that act on that row column by column: &, |, ^ and ~, and the shifts << and >>. This lesson teaches how to compute them by hand, how to use them to store several flags in a single integer with the technique of masks, and how to recognize the shifts that the standard leaves undefined. It then explains why 2 ^ 3 is 1 and not 8, and why the bitwise operators demand parentheses. The second half presents the math library: the functions of <cmath>, the constants of <numbers>, the greatest common divisor and the least common multiple of <numeric> and the bit functions of <bit>, with a principle that holds in any language: what the library offers correct and tested is not rewritten.

Learning objectives

Compute by hand the result of &, |, ^, ~ and of the shifts on small integers.
Distinguish the defined shifts (including those of negative numbers, since C++20) from those that are undefined behavior, and predict the result of the former.
Use masks to test, set, clear and toggle a bit.
Explain why 2 ^ 3 is 1 and not 8, and choose between std::pow and a shift according to the case.
Use functions of <cmath> (std::sqrt, std::pow, std::abs, std::hypot, the trigonometric ones) and the constants of <numbers>, such as std::numbers::pi, in formulas.

Bitwise operators

The lesson Integers and their representation showed that an int is a row of bits, 32 on the systems of the course, and that its value is the sum of the weights of the positions holding a 1. Up to now, however, the program has treated the integer only as a number: it has added, multiplied and divided it. Now, the same row admits another reading, as a collection of 32 yes-or-no answers, and for that reading C++ has four operators that work on the bits one by one, with no carry between positions.

The bits are numbered from the right, starting at 0: bit $k$ is the one of weight $2^k$ . Thus, in $12$ , which is 1100 in binary, bits 2 and 3 are set, and bits 0 and 1 are clear.

The operators are these. The bitwise AND, a & b, has a 1 in each position where a and b both have a 1. The bitwise OR, a | b, has a 1 where at least one of the two has one. The XOR, a ^ b, has a 1 where exactly one of the two has one, that is, where the bits differ. The bitwise NOT, ~a, has a single operand and inverts each bit. The tables of the first three, for a pair of bits $p$ and $q$ , are those of conjunction, disjunction and exclusive disjunction:

\begin{array}{cc|ccc} p & q & p \mathbin{\&} q & p \mid q & p \mathbin{\hat{}} q \\ \hline 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}

Whoever has studied the course Mathematical Logic I will recognize here the propositional connectives, with 1 for true and 0 for false: a bitwise operator is nothing other than a connective applied to all the columns at once. From this follows the method of computing by hand: write the two numbers in binary, one above the other, aligned on the right, and apply the table in each column, without paying attention to its neighbors.

ExampleTwelve and ten, column by column

The numbers $12 =$ 1100 and $10 =$ 1010 have the property that their four columns run through the four combinations of two bits; that is why they serve to see the three tables at once.

Proof

The data: 1100 is 12 and 1010 is 10. The columns, from left to right, hold the pairs $(1, 1)$ , $(1, 0)$ , $(0, 1)$ and $(0, 0)$ .
First column of 12 & 10: both bits are 1, and the AND gives 1.
Second column: 1 and 0. A single 0 is enough for the AND to give 0.
Third column: 0 and 1; the AND gives 0 again.
Fourth column: 0 and 0 give 0. The result row, 1000, is 8: 12 & 10 is 8.
The OR sets every column that has at least one 1: 1110, that is, 12 | 10 is 14.
The XOR sets only the columns whose bits differ: 0110, and 12 ^ 10 is 6.

The following program checks the figure. The format specification {:04b}, presented in the lesson on integers, writes a value in binary with four digits, padded with zeros.

C++ program

#include <print>int main(){    const int a{0b1100};    const int b{0b1010};    std::println("a     = {:04b} = {}", a, a);    std::println("b     = {:04b} = {}", b, b);    std::println("a & b = {:04b} = {}", a & b, a & b);    std::println("a | b = {:04b} = {}", a | b, a | b);    std::println("a ^ b = {:04b} = {}", a ^ b, a ^ b);    std::println("~a    = {}", ~a);}

Output

a     = 1100 = 12b     = 1010 = 10a & b = 1000 = 8a | b = 1110 = 14a ^ b = 0110 = 6~a    = -13

The last line deserves an explanation. The NOT inverts the 32 bits of a, not only the four that are written: the 28 zeros on the left become ones, and an int that begins with 1 is negative in two’s complement. Now, in two’s complement the opposite of a number is obtained by inverting its bits and adding 1, that is, $-x = {\sim}x + 1$ ; therefore, ${\sim}x = -x - 1$ , and ~12 is $-13$ . The bitwise NOT of a signed integer thus gives a number that rarely matters as a number: it matters as a pattern, and that is why bits are preferably manipulated in unsigned types, as the section on masks will show.

A warning about small types. Before operating, C++ converts to int every operand of a narrower integer type, such as std::uint8_t; this is the promotion that the lesson Arithmetic described for the arithmetic operations, and it applies here too. It follows that ~flags, with flags of type std::uint8_t and value 5, is not the byte 11111010, but the int $-6$ , whose 32 bits include 24 ones added on the left; only when it is stored again in a std::uint8_t is it cut down to eight bits and the expected byte, 250, recovered.

The bitwise operators must not be confused with the logical operators of the lesson Relations and logic. 6 && 3 is true: both operands are nonzero, and the result is a bool. 6 & 3, by contrast, is an integer, the one formed by the columns where both have a 1. Moreover, && is evaluated with short-circuit evaluation and & always evaluates both operands.