Vai al contenuto
Topos Uranos
Italiano

Bit e libreria matematica

Riepilogo

Per il processore un intero è una fila di bit, e C++ offre operatori che agiscono su quella fila colonna per colonna: &, |, ^ e ~, e gli scorrimenti << e >>. Questa lezione insegna a calcolarli a mano, a usarli per conservare diversi flag in un solo intero con la tecnica delle maschere, e a riconoscere gli scorrimenti che lo standard non definisce. Spiega poi perché 2 ^ 3 vale 1 e non 8, e perché gli operatori bit a bit esigono le parentesi. La seconda metà presenta la libreria matematica: le funzioni di <cmath>, le costanti di <numbers>, il massimo comune divisore e il minimo comune multiplo di <numeric> e le funzioni sui bit di <bit>, con un principio che vale in qualsiasi linguaggio: ciò che la libreria offre corretto e collaudato non si riscrive.

Obiettivi di apprendimento

  1. Calcolare a mano il risultato di &, |, ^, ~ e degli scorrimenti su interi piccoli.
  2. Distinguere gli scorrimenti definiti (anche quelli dei negativi, da C++20) da quelli che sono comportamento indefinito, e prevedere il risultato dei primi.
  3. Usare maschere per consultare, accendere, spegnere e invertire un bit.
  4. Spiegare perché 2 ^ 3 vale 1 e non 8, e scegliere tra std::pow e uno scorrimento secondo il caso.
  5. Usare funzioni di <cmath> (std::sqrt, std::pow, std::abs, std::hypot, le trigonometriche) e le costanti di <numbers>, come std::numbers::pi, nelle formule.

Operatori bit a bit

La lezione Gli interi e la loro rappresentazione ha mostrato che un int è una fila di bit, 32 nei sistemi del corso, e che il suo valore è la somma dei pesi delle posizioni in cui c’è un 1. Finora, tuttavia, il programma ha trattato l’intero solo come un numero: lo ha sommato, moltiplicato e diviso. Ora, la stessa fila ammette un’altra lettura, come una collezione di 32 risposte sì o no, e per questa lettura C++ ha quattro operatori che lavorano sui bit uno per uno, senza riporto tra le posizioni.

I bit si numerano da destra, cominciando da 0: il bit kk è quello di peso 2k2^k. Così, nel numero 1212, che in binario è 1100, sono accesi i bit 2 e 3, e spenti i bit 0 e 1.

Gli operatori sono questi. L’AND bit a bit, a & b, ha un 1 in ogni posizione in cui a e b hanno entrambi un 1. L’OR bit a bit, a | b, ha un 1 dove almeno uno dei due ce l’ha. Lo XOR, a ^ b, ha un 1 dove esattamente uno dei due ce l’ha, cioè dove i bit differiscono. La negazione bit a bit, ~a, ha un solo operando e inverte ogni bit. Le tabelle dei primi tre, per una coppia di bit pp e qq, sono quelle della congiunzione, della disgiunzione e della disgiunzione esclusiva:

pqp&qp∣qp^q11110100110101100000\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}

Chi ha studiato il corso Logica Matematica I riconoscerà qui i connettivi proposizionali, con 1 per vero e 0 per falso: un operatore bit a bit non è altro che un connettivo applicato a tutte le colonne insieme. Ne segue il metodo di calcolo a mano: si scrivono i due numeri in binario, uno sopra l’altro, allineati a destra, e si applica la tabella in ogni colonna, senza occuparsi delle vicine.

EsempioDodici e dieci, colonna per colonna

I numeri 12=12 = 1100 e 10=10 = 1010 hanno la proprietà che le loro quattro colonne percorrono le quattro combinazioni di due bit; per questo servono a vedere le tre tabelle insieme.

Dimostrazione

  1. I dati: 1100 è 12 e 1010 è 10. Le colonne, da sinistra a destra, hanno le coppie (1,1)(1, 1), (1,0)(1, 0), (0,1)(0, 1) e (0,0)(0, 0).

  2. Prima colonna di 12 & 10: entrambi i bit sono 1, e l’AND dà 1.

  3. Seconda colonna: 1 e 0. Basta uno 0 perché l’AND dia 0.

  4. Terza colonna: 0 e 1; l’AND dà di nuovo 0.

  5. Quarta colonna: 0 e 0 danno 0. La fila risultato, 1000, è 8: 12 & 10 vale 8.

  6. L’OR accende ogni colonna che abbia almeno un 1: 1110, cioè 12 | 10 vale 14.

  7. Lo XOR accende solo le colonne i cui bit differiscono: 0110, e 12 ^ 10 vale 6.

Il programma seguente verifica la figura. La specifica di formato {:04b}, presentata nella lezione sugli interi, scrive un valore in binario con quattro cifre, completate con zeri.

Programma in 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);}
Output
a     = 1100 = 12b     = 1010 = 10a & b = 1000 = 8a | b = 1110 = 14a ^ b = 0110 = 6~a    = -13

L’ultima riga merita una spiegazione. La negazione inverte i 32 bit di a, non solo i quattro che si scrivono: i 28 zeri di sinistra diventano degli uno, e un int che comincia con 1 è negativo in complemento a due. Ora, in complemento a due l’opposto di un numero si ottiene invertendone i bit e sommando 1, cioè −x=∼x+1-x = {\sim}x + 1; quindi ∼x=−x−1{\sim}x = -x - 1, e ~12 vale −13-13. La negazione bit a bit su un intero con segno dà, dunque, un numero che raramente interessa come numero: interessa come configurazione, e per questo i bit si manipolano di preferenza in tipi senza segno, come si vedrà nella sezione sulle maschere.

Un’avvertenza sui tipi piccoli. Prima di operare, C++ converte in int ogni operando di un tipo intero più stretto, come std::uint8_t; è la promozione che la lezione Aritmetica ha descritto per le operazioni aritmetiche, e vale anche qui. Ne segue che ~flags, con flags di tipo std::uint8_t e valore 5, non è il byte 11111010, ma l’int −6-6, i cui 32 bit includono 24 uno aggiunti a sinistra; solo quando lo si conserva di nuovo in un std::uint8_t esso viene ridotto a otto bit e si recupera il byte atteso, 250.

Non si devono confondere gli operatori bit a bit con gli operatori logici della lezione Relazioni e logica. 6 && 3 è true: entrambi gli operandi sono diversi da zero, e il risultato è un bool. 6 & 3, invece, è un intero, quello formato dalle colonne in cui entrambi hanno un 1. Inoltre, && si valuta a cortocircuito e & valuta sempre entrambi gli operandi.