Menu
Coddy logo textTech
INIZIA A IMPARARE
flag It iconItalianodown icon

Numero di bit impostati

Lezione 11 di 17 del corso Manipolazione dei bit di Coddy.

Per cominciare, cosa sono i bit impostati?

Nei termini informatici, la cifra «1» nei numeri binari è nota come bit impostato.

In questa lezione vogliamo calcolare

il numero di bit impostati presenti nella rappresentazione binaria del numero dato.

Per esempio, supponiamo di avere il numero (20)10 in binario (10100)2 : il numero di bit impostati presenti in (20)10 è 2.

Prova a pensare a un approccio. Probabilmente penserai di convertire il numero nella sua forma binaria e contare il numero di uno, va bene, ma che dire dei numeri grandi? Non potrai memorizzarli nel tipo di dato integer; come potremo conoscere il numero di bit impostati nei numeri grandi? La risposta, ovviamente, è la manipolazione dei bit!

  • Per prima cosa prendiamo una variabile di posizione, chiamiamola pos, per sapere quale bit si trova in una determinata posizione nel numero binario.
  • Poi eseguiamo uno shift a sinistra di pos posizioni su «1».
  • Infine eseguiamo semplicemente un'operazione AND con il numero dato.

In che modo è utile? Vediamolo con il numero (20)10:

  • Per la prima posizione, pos=0. 20 & 1<<pos , 1<<pos=1 ed eseguire l'operazione AND su (10100)2 e (00001)2 dà come risultato zero.
  • Per la seconda posizione, pos=1. 20 & 1<<pos, 1<<pos=(10)2 ed eseguire l'operazione AND su (10100)2 e (00010)2 dà come risultato zero.
  • Per la terza posizione, pos=2. 20 & 1<<pos, 1<<pos=(100)2 ed eseguire l'operazione AND su (10100)2 e (00100)2 dà come risultato uno, ovvero il nostro primo bit impostato.
  • Per la quarta posizione, pos=2. 20 & 1<<pos, 1<<pos=(1000)2 ed eseguire l'operazione AND su (10100)2 e (01000)2 dà come risultato zero.
  • Per la terza posizione, pos=2. 20 & 1<<pos, 1<<pos=(10000)2 ed eseguire l'operazione AND su (10100)2 e (10000)2 dà come risultato uno, ovvero il secondo bit impostato.

Per contare il numero di bit impostati possiamo usare una variabile contatore. Spero però che questo esempio abbia chiarito l'algoritmo.

In questo modo possiamo calcolare facilmente il numero di bit impostati presenti nella rappresentazione binaria di un numero, senza preoccuparci di superare l'intervallo del tipo di dato int in C++.

challenge icon

Sfida

Medio

Completa la funzione SetBits per restituire il numero di bit impostati nel numero dato utilizzando l'approccio descritto sopra.

Provalo tu

#include <cmath>

int SetBits(int num) {
    // Scrivi il codice qui
}

Tutte le lezioni di Manipolazione dei bit

1Introduzione e basi

Cos’è la manipolazione dei bit?Perché serve la manipolazione dei bit?Numeri binari e decimaliOperatori NOT e OROperatore ANDOperatore XOROperatori di shift a destra e a sinistraRiepilogo degli operatori bitwise

2Algoritmi sui bit

Potenza di 2Numero che ricorre un numero dispari di volteNumero di bit impostatiRotazione dei bit di un numero IRotazione dei bit di un numero II

3Sfide pratiche

Tina e l’assegnazione dei bitXORtyTrova KTrova la somma minima

Esercitati da solo: Compilatore C++ online