Algoritmi classici di manipolazione dei bit e relative classiche domande da intervista tecnica

Gli algoritmi di manipolazione dei bit permettono, in maniera elegante ed efficacie, di risolvere problemi come il trovare l’ultima cifra significativa di un numero rappresentato in binario (LSB, dall’inglese Least Significant Bit), oppure il contare il numero di setbit (ovvero bit pari a 1) in un numero qualsiasi codificato in binario. Queste domande sono spesso poste durante colloqui di lavoro presso grandi società, come Google e Amazon.

• Valutiamo ora il problema del trovare l’ultima cifra significativa di un numero N rappresentato in binario. Per farlo, si utilizza l’operatore logico And in VB.NET, equivalente in C# all’operatore &, eseguendo l’operazione N And 1. In questo modo il programma valuterà solo l’ultimo bit del numero N e restituirà 1 se è pari a 1, 0 altrimenti. In questo modo, è possibile agilmente creare un programma per controllare se un numero risulta essere dispari o meno (poichè, se dispari, terminerà con un 1 nella sua codifica in binario). In C# : . IsEven(int N){ . if((int Valore: LSB = N & 1) == 0){ . return True . } else{ . return False . } .} .
• Per quanto concerne il contare il numero di setbit, anche questo quesito può essere svolto elegantemente. Si può costruire un algoritmo Naive andando a complicare leggermente la soluzione del quesito precedente. Abbiamo infatti visto come è possibile valutare l’ultimo bit di un numero N codificato in binario. A questo punto, tramite l’operatore di scorrimento shift, identificato in C# e in VB.NET con il simbolo “>>“, è possibile traslare di una posizione verso destra i bit che compongono la sequenza della rappresentazione binaria di N. Si procederà quindi a valutare iterativamente l’ultimo bit significativo, fino a che il numero di partenza non sarà pari a 0.  Algoritmo di Naive, in VB: . . Do While N <> 0 . SumSetBit += N And 1 . N = N >> 1 . Loop .
• Per eseguire il conteggio del numero di set bit si può procedere anche utilizzando il seguente algoritmo detto di Kernhigan: . . Function ContatoreSetBit(N As Integer) As Integer . Dim ContetatoreSetBit As Integer = 0 . do while N<>0 . N = N And(N-1) . ContatoreSetBit +=1 . Loop . In sostanza consiste nel contare tutti gli 1 della rappresentazione binaria del numero intero N, pertanto le volte che è stata eseguita l’operazione si è indirettamente anche contato gli 1 presenti. Questo algoritmo risulta essere molto più efficiente del precedente in quanto ha una complessità computazionale inevitabilmente minore.
• Per trovare la potenza di due massima che divide l’intero dato basta eseguire la seguente operazione: N And Not (N-1) .

Tipiche domande per colloqui di lavoro riguardanti operazioni con operatori bitwise sono:

• Trovare il segno di un intero;
• Controllare se due interi hanno lo stesso segno;
• Scrivere un programma per controllare se un numero è una potenza di 2;
• Come impostare un k-esimo bit;
• Come resettare un k-esimo bit;
• Scrivere un programma per contare i set bit di un intero;
• Calcolare il minimo (min) o il massimo (max) di due interi senza branching;
• Scambiare due numeri senza usare una terza variabile;
• Cancellare tutti i bit dal LSB al i-esimo bit;
• Come prendere l’i-esimo un bit da un numero intero.