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

[vict85]

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:

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).

[vict85]

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

Codice:

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

[ZfreS]

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 :

Codice:

int ruota_bit(int num, int shift)
{
   return (num << shift) | (num >> (32 - shift));
}


e poi nel main:

Codice:

cout << ruota_bit(26, 3) << endl;


Il problema è che non funziona. Praticamente fa semplicemente lo shift a sinistra. Potreste aiutarmi a capire dove sbaglio?

[Obidream]

Codice:

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?

[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.

[Obidream]

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?

[ZfreS]

Scusami, ma non ho capito la domanda. Il $26$ in binario lo rappresento sempre in quel modo. A quanto devono essere segnati i bit?

[Obidream]

Come sarebbe in questo caso il circular left shift di 3 step?

$00000000$ $00000000$ $00000000$ $00011010$

[ZfreS]

Sarebbe questo: $00000000$ $00000000$ $00000000$ $00010110$

[Obidream]

Sarebbe questo: $00000000 00000000 00000000 11010000$

Ottimo ed in decimale quant'è?

P.s Vedi che ha senso specificare su quanti bit si sta lavorando?