ビットと数学ライブラリ

要約

整数はプロセッサにとってビットの並びであり、C++ はその並びに桁ごとに作用する演算子を備えている。&、|、^、~、そしてシフト << と >> である。このレッスンでは、それらを手で計算する方法、マスクの技法で一つの整数に複数のフラグを保持する方法、規格が定義しないシフトを見分ける方法を学ぶ。続いて、なぜ 2 ^ 3 が 8 ではなく 1 になるのか、なぜビット演算子には括弧が必要なのかを説明する。後半では数学ライブラリを紹介する。<cmath> の関数、<numbers> の定数、<numeric> の最大公約数と最小公倍数、<bit> のビット関数であり、どの言語でも通用する原則を添える。ライブラリが正しく検証済みの形で提供するものは書き直さない、という原則である。

学習目標

小さな整数について、&、|、^、~ とシフトの結果を手で計算する。
定義されたシフト（C++20 以降は負の数のシフトも含む）と未定義の動作であるシフトを区別し、前者の結果を予測する。
マスクを使って、ビットを調べ、立て、下ろし、反転する。
なぜ 2 ^ 3 が 8 ではなく 1 になるのかを説明し、場合に応じて std::pow とシフトを使い分ける。
<cmath> の関数（std::sqrt、std::pow、std::abs、std::hypot、三角関数）と <numbers> の定数、たとえば std::numbers::pi を式の中で使う。

ビット演算子

レッスン整数とその表現では、int がビットの並び（このコースのシステムでは 32 ビット）であり、その値は 1 が立っている位置の重みの和であることを見た。しかしこれまで、プログラムは整数を数としてしか扱ってこなかった。足し、掛け、割ってきただけである。ところが、同じ並びには別の読み方もある。32 個の「はい」か「いいえ」の答えの集まりとして読むのであり、この読み方のために C++ には、ビットを一つずつ、位置の間の繰り上がりなしに扱う四つの演算子がある。

ビットは右から 0 始まりで番号を付ける。ビット $k$ とは重み $2^k$ のビットである。たとえば $12$ （二進法で 1100）では、ビット 2 と 3 が立っており、ビット 0 と 1 が下りている。

演算子は次のとおりである。ビットごとの AND a & b は、a と b の両方が 1 である各位置で 1 になる。ビットごとの OR a | b は、二つのうち少なくとも一方が 1 である位置で 1 になる。ビットごとの XOR a ^ b は、二つのうちちょうど一方が 1 である位置、つまりビットが異なる位置で 1 になる。ビットごとの NOT ~a はオペランドを一つだけとり、各ビットを反転する。一組のビット $p$ と $q$ についての最初の三つの表は、連言、選言、排他的選言の表である。

\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}

コース『数理論理学 I』を学んだ人は、ここに命題の結合子を見て取るだろう。1 が真、0 が偽を表す。ビット演算子とは、すべての桁に同時に適用される結合子にほかならない。ここから手計算の方法が導かれる。二つの数を二進法で上下に並べて右端をそろえ、各桁に表を適用する。隣の桁は気にしなくてよい。

例12 と 10、桁ごとに

数 $12 =$ 1100 と $10 =$ 1010 には、四つの桁が二つのビットの四通りの組合せをすべてたどるという性質がある。そのため、三つの表を一度に見るのに向いている。

証明

データ：1100 は 12、1010 は 10 である。桁は左から右へ、組 $(1, 1)$ 、 $(1, 0)$ 、 $(0, 1)$ 、 $(0, 0)$ をもつ。
12 & 10 の第 1 桁：両方のビットが 1 なので、AND は 1 になる。
第 2 桁：1 と 0。0 が一つあれば AND は 0 になる。
第 3 桁：0 と 1。AND はやはり 0 になる。
第 4 桁：0 と 0 で 0 になる。結果の並び 1000 は 8 であり、12 & 10 は 8 である。
OR は少なくとも一つの 1 がある桁をすべて立てる。1110、つまり 12 | 10 は 14 である。
XOR はビットが異なる桁だけを立てる。0110 であり、12 ^ 10 は 6 である。

以下のプログラムで図を確かめる。整数のレッスンで紹介した書式フィールド {:04b} は、値を二進法の 4 桁で、足りない分を 0 で埋めて書く。

C++ のプログラム

#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);}

出力

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

最後の行には説明が要る。NOT は書かれている 4 ビットだけでなく、a の 32 ビットすべてを反転する。左側の 28 個の 0 は 1 になり、1 で始まる int は 2 の補数では負である。ところで、2 の補数では、ある数の反数はビットを反転して 1 を足すと得られる。すなわち $-x = {\sim}x + 1$ である。したがって ${\sim}x = -x - 1$ であり、~12 は $-13$ になる。符号付き整数に対するビットごとの NOT は、数としてはめったに意味のない数を与える。意味があるのはビットパターンとしてであり、そのためビットの操作はなるべく符号なし型で行う。マスクの節で見るとおりである。

小さな型についての注意。演算の前に、C++ は std::uint8_t のようなより狭い整数型のオペランドをすべて int に変換する。これはレッスン算術演算が算術演算について述べた昇格であり、ここでも同じく働く。したがって、flags が std::uint8_t 型で値が 5 のとき、~flags はバイト 11111010 ではなく int の $-6$ であり、その 32 ビットには左に付け加えられた 24 個の 1 が含まれる。std::uint8_t に格納し直してはじめて 8 ビットに切り詰められ、期待どおりのバイト 250 が得られる。

ビット演算子を、レッスン関係と論理の論理演算子と混同してはならない。6 && 3 は true である。両オペランドとも 0 でなく、結果は bool である。一方、6 & 3 は整数であり、両方に 1 がある桁からなる。さらに、&& は短絡評価されるが、& は常に両方のオペランドを計算する。