[C, C++] Difficoltà a capire gli operatori bitwise

Messaggioda ZfreS » 29/10/2019, 20:27

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?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1896 di 4589
Iscritto il: 22/10/2016, 17:52

Re: [C, C++] Difficoltà a capire gli operatori bitwise

Messaggioda Quinzio » 29/10/2019, 20:54

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<<k) prendo il suo
predecessore (1<<k)-1 e li mette in and bitwise (&).
Codice:
#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.
Codice:
0000 0000  1000 0000
0000 0000  0111 1111
---- ----  ---- ----
0000 0000  0000 0000
Quinzio
Cannot live without
Cannot live without
 
Messaggio: 4347 di 10487
Iscritto il: 24/08/2010, 06:50

Re: [C, C++] Difficoltà a capire gli operatori bitwise

Messaggioda ZfreS » 29/10/2019, 21:19

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.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1897 di 4589
Iscritto il: 22/10/2016, 17:52

Re: [C, C++] Difficoltà a capire gli operatori bitwise

Messaggioda vict85 » 29/10/2019, 21:41

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*}
vict85
Moderatore
Moderatore
 
Messaggio: 9927 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: [C, C++] Difficoltà a capire gli operatori bitwise

Messaggioda ZfreS » 29/10/2019, 21:54

Grazie vict per la formula!
Grazie tante Sergio per la spiegazione dettagliata!
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1898 di 4589
Iscritto il: 22/10/2016, 17:52

Re: [C, C++] Difficoltà a capire gli operatori bitwise

Messaggioda vict85 » 29/10/2019, 22:59

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)
vict85
Moderatore
Moderatore
 
Messaggio: 9928 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: [C, C++] Difficoltà a capire gli operatori bitwise

Messaggioda ZfreS » 30/10/2019, 16:04

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:
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
Cannot live without
Cannot live without
 
Messaggio: 1899 di 4589
Iscritto il: 22/10/2016, 17:52

Re: [C, C++] Difficoltà a capire gli operatori bitwise

Messaggioda vict85 » 30/10/2019, 16:51

ZfreS ha scritto: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 ha scritto: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:
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.
vict85
Moderatore
Moderatore
 
Messaggio: 9930 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: [C, C++] Difficoltà a capire gli operatori bitwise

Messaggioda ZfreS » 30/10/2019, 17:14

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
Cannot live without
Cannot live without
 
Messaggio: 1900 di 4589
Iscritto il: 22/10/2016, 17:52

Re: [C, C++] Difficoltà a capire gli operatori bitwise

Messaggioda vict85 » 30/10/2019, 17:21

ZfreS ha scritto: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?
vict85
Moderatore
Moderatore
 
Messaggio: 9931 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Prossimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Google [Bot] e 1 ospite