[C, C++] Difficoltà a capire gli operatori bitwise
Studiando c++ ho incontrato gli operatori bitwise che ho messo da parte per ritornarci più avanti. Ora che è arrivato il momento di farlo, sto trovando difficoltà nel capirli. Quello che ho capito è come funziona l'and a livello di bit, come funzione l'or, lo xor ecc, ma non riesco a capire come funzionano certi algoitmi che ne fanno uso. Per esempio non capisco perchè facendo l'and tra un numero e il suo precedente che viene 0, allora il numero è una potenza di 2. Non capisco davvero come si arrivi a questo risultato, come si dimostra? Potreste chiarirmi quest'ultimo e ingenerale darmi un consiglio su come capire questo genere di algoritmi?
Risposte
Ma guarda, fossi in te non mi preoccuperei... non c'e' molto da capire.
Si tratta a volte di trucchetti di basso livello.
Ad esempio questo programmino prende un numero potenza di due (1<
Se e' vero che il risultato e' zero, scrive "true".
Ad esempio nel riquadro sotto:
prendiamo un numero a 16 bit potenza di due, in codice binario, 128
e il suo predecessore 127 e poi facciamo l'ando bitwise, ovvero bit a bit,
ovvero prendiamo ogni colonna singolarmente e calcoliamo l'and tra il bit sopra
e il bit sotto. Il risultato e' zero.
Si tratta a volte di trucchetti di basso livello.
Ad esempio questo programmino prende un numero potenza di due (1<
#include <stdio.h>
int main()
{
unsigned int k = 5;
printf("%b\n", 1<<k);
printf("%b\n", (1<<k)-1);
if ((1<<k & (1<<k)-1) == 0)
printf ("true !\n");
else
printf ("false !\n");
}
Se e' vero che il risultato e' zero, scrive "true".
Ad esempio nel riquadro sotto:
prendiamo un numero a 16 bit potenza di due, in codice binario, 128
e il suo predecessore 127 e poi facciamo l'ando bitwise, ovvero bit a bit,
ovvero prendiamo ogni colonna singolarmente e calcoliamo l'and tra il bit sopra
e il bit sotto. Il risultato e' zero.
0000 0000 1000 0000 0000 0000 0111 1111 ---- ---- ---- ---- 0000 0000 0000 0000
Ok, in effetti provando e riprovando è vero. Ma è matematematicamente dimostrabile questa proprietà? Certo che sono trucchetti, ma è sapere fare queste cose abilemente a determinare la bravura di un programmatore, ma ho l'impressione che molti imparino le cose senza capirne a fondo il perchè. Infatti consultando vari siti non ho trovato una spiegazione del perchè funzionino e che ragionamento deduttivo ci sia dietro.
Si lo è. Deriva dal fatto che \(2^n - 1 = \sum_{i=0}^{n-1} 2^{i}\).
Visto in maniera un po' più visiva:
\begin{align*} 1 + \sum_{i=0}^{n-1} 2^{i} &= 1 + ( 1 + 2 + 4 + 8 + \dotsb + 2^{n-1}) \\
&= 2 + 2 + 4 + 8 + \dotsb + + 2^{n-1} \\
&= 4 + 4 + 8 + \dotsb + + 2^{n-1} \\
&= 8 + 8 + \dotsb + + 2^{n-1} \\
&\quad\vdots\\
&= 2^{n-1} + 2^{n-1} \\
&= 2^{n} \\
\end{align*}
Visto in maniera un po' più visiva:
\begin{align*} 1 + \sum_{i=0}^{n-1} 2^{i} &= 1 + ( 1 + 2 + 4 + 8 + \dotsb + 2^{n-1}) \\
&= 2 + 2 + 4 + 8 + \dotsb + + 2^{n-1} \\
&= 4 + 4 + 8 + \dotsb + + 2^{n-1} \\
&= 8 + 8 + \dotsb + + 2^{n-1} \\
&\quad\vdots\\
&= 2^{n-1} + 2^{n-1} \\
&= 2^{n} \\
\end{align*}
Grazie vict per la formula!
Grazie tante Sergio per la spiegazione dettagliata!
Grazie tante Sergio per la spiegazione dettagliata!
Prego. Comunque queste cose compaiono più nei colloqui di lavoro che nel lavoro effettivo. E per la preparazione ai colloqui esiste tantissimo materiale. Per esempio, ecco un problema da colloquio che può essere risolto usando gli operatori bitwise: https://leetcode.com/problems/missing-number/ (oltre che in almeno altri 4 modi diversi). Ci sono le soluzioni, penso aperte anche agli utenti non premium. Se non lo sono posso eventualmente farti un riassunto io. Ti suggerisco di provare a risolverlo da solo però (non concentrarti subito sulla soluzione bitwise, è decisamente la meno intuitiva)
Questo è un problema davvero semplice se l'array è ordinato. Infatti basta fare un ciclo e vedere se il massimo numero ha un numero che lo precede. In questo caso, senza troppo sforzo, immagino una soluzione usando l'operatore bitwise xor, in quanto lo xor tra due numeri uguali è zero. Se lo metto in un ciclo, l'indice i dell'array fara lo xor con l'elemento corrispondente finchè questo sarà diverso da zero. Ecco il codice:
int trovaElementoMancante(int arr[], int num_cifre)
{
int i = 0;
int a = 0;
while (a == 0 && i != num_cifre)
{
a = i xor arr[i];
i++;
}
return i - 1;
}
"ZfreS":
Questo è un problema davvero semplice se l'array è ordinato. Infatti basta fare un ciclo e vedere se il massimo numero ha un numero che lo precede.
Basta confrontare il numero con l'indice di un ciclo for. Ovviamente la complessità totale è comunque dominata dall'ordinamento (che per std::sort è verosimilmente \(O(n\log n)\)).
"ZfreS":
In questo caso, senza troppo sforzo, immagino una soluzione usando l'operatore bitwise xor, in quanto lo xor tra due numeri uguali è zero. Se lo metto in un ciclo, l'indice i dell'array fara lo xor con l'elemento corrispondente finchè questo sarà diverso da zero. Ecco il codice:
int trovaElementoMancante(int arr[], int num_cifre) { int i = 0; int a = 0; while (a == 0 && i != num_cifre) { a = i xor arr[i]; i++; } return i - 1; }
Così a occhio, il tuo codice non funziona se i numeri non sono in ordine.
Ovviamente esiste la possibilità di usare un hash set per trovare l'elemento in \(O(n)\), ma è poco elegante e usa \(O(n)\) memoria aggiuntiva. Una soluzione alternativa con complessità \(O(n)\) e memoria \(O(1)\) è ispirata a Gauss.
Certo, fare la somma tra i numeri che dovrebbero esserci e sotrarre la somma dei numeri che ci sono. Ma la mia soluzione bitwise è corretta?
"ZfreS":
Certo, fare la somma tra i numeri che dovrebbero esserci e sotrarre la somma dei numeri che ci sono. Ma la mia soluzione bitwise è corretta?
L'idea è nella direzione giusta, ma il codice non è corretto. Comunque, supponendo che tu non avessi a disposizione un sito come quello che ti ho mostrato (che controlla la tua soluzione) o un'altra persona che ti controlla il codice, come potresti controllare se il tuo codice è corretto?
Il problema era definito nel mio link a leetcode.com (un sito di esercizi di programmazione per la preparazione ai colloqui o semplicemente perché ti piace risolvere problemi con la programmazione). Il problema è il seguente:
Il problema è ovviamente facile e avevo linkato la pagina perché è un problema per cui LeetCode fornisce delle soluzioni (in Java e Python3 ma cambia poco).
"LeetCode":
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
Example 1:
Input: [3,0,1]
Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Il problema è ovviamente facile e avevo linkato la pagina perché è un problema per cui LeetCode fornisce delle soluzioni (in Java e Python3 ma cambia poco).
Comunque il problema della tua soluzione è che pensavi di dover fare lo xor tra due soli elementi per volta, mentre era la soluzione prevede che tu faccia lo xor tra \(2n - 1\) elementi diversi.
Segno gli elementi dell'array con \(n_{i}\) e lo xor con \(\veebar\). Considera quindi \[ x = 0 \veebar 1 \veebar \dotsb \veebar (n-1) \veebar n \veebar n_0 \veebar n_1 \veebar \dotsb \veebar n_{n-1}\,. \]
Se \(i\) è il numero mancante allora per ipotesi hai che \[\begin{align*} x &= ( 0 \veebar 0 ) \veebar \dotsb \veebar
\bigl[ (i-1) \veebar (i-1) \bigr] \veebar i \veebar \bigl[ (i+1) \veebar (i+1) \bigr] \veebar
\dotsb \veebar ( n \veebar n ) \\
&= i \,. \end{align*}\]
Quindi alla fine il codice è qualcosa come
Segno gli elementi dell'array con \(n_{i}\) e lo xor con \(\veebar\). Considera quindi \[ x = 0 \veebar 1 \veebar \dotsb \veebar (n-1) \veebar n \veebar n_0 \veebar n_1 \veebar \dotsb \veebar n_{n-1}\,. \]
Se \(i\) è il numero mancante allora per ipotesi hai che \[\begin{align*} x &= ( 0 \veebar 0 ) \veebar \dotsb \veebar
\bigl[ (i-1) \veebar (i-1) \bigr] \veebar i \veebar \bigl[ (i+1) \veebar (i+1) \bigr] \veebar
\dotsb \veebar ( n \veebar n ) \\
&= i \,. \end{align*}\]
Quindi alla fine il codice è qualcosa come
uint32_t
trovaElementoMancante( uint32_t arr[], uint32_t num_cifre )
{
uint32_t ans = num_cifre;
for ( uint32_t i = 0; i != num_cifre; ++i )
{
ans ^= ( i ^ arr[ i ] );
}
return ans;
}
Ho capito, facendo lo xor tra gli elementi dell'array e gli elementi che dovrebbero esserci, non fà 0 perchè sono diversi ma restituisce il numero mancante che fa la "differenza". Avrei invece problemi con un altro esercizio: usare gli operatori bitwise per fare il cosidetto circular shift (sinistro). A tale scopo ho implementato la seguente logica :
e poi nel main:
Il problema è che non funziona. Praticamente fa semplicemente lo shift a sinistra. Potreste aiutarmi a capire dove sbaglio?
int ruota_bit(int num, int shift)
{
return (num << shift) | (num >> (32 - shift));
}
e poi nel main:
cout << ruota_bit(26, 3) << endl;
Il problema è che non funziona. Praticamente fa semplicemente lo shift a sinistra. Potreste aiutarmi a capire dove sbaglio?
"ZfreS":
cout << ruota_bit(26, 3) << endl;
Al di là del codice che andrebbe discusso con calma, mi faresti vedere i passaggi a mano di questo conto per vedere che risultato ti aspetti?
Per esempio in quel caso, i bit del 26 sono: $011010$ che con l'operazione di shift sinistro ruotato di 3 diventa $010011$ che corrisponde al 19. Eseguendo il programma però viene 208.
"ZfreS":
Per esempio in quel caso, i bit del 26 sono: $011010$ che con l'operazione di shift sinistro ruotato di 3 diventa $010011$ che corrisponde al 19. Eseguendo il programma però viene 208.
Ora facciamo un'altra prova, facciamo finta di lavorare con degli interi non segnati a $32$ bit. Come rappresenti il $26$ in questo caso?
Scusami, ma non ho capito la domanda. Il $26$ in binario lo rappresento sempre in quel modo. A quanto devono essere segnati i bit?
Come sarebbe in questo caso il circular left shift di 3 step?
$00000000$ $00000000$ $00000000$ $00011010$
$00000000$ $00000000$ $00000000$ $00011010$
Sarebbe questo: $00000000$ $00000000$ $00000000$ $00010110$
"ZfreS":
Sarebbe questo: $00000000 00000000 00000000 11010000$
Ottimo ed in decimale quant'è?
P.s Vedi che ha senso specificare su quanti bit si sta lavorando?
In decimale è $22$. Ma perchè il mio codice non funziona?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo