Shoot for the Stats

Gli algoritmi di manipolazione dei bits 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.

Determinare il LSB di N

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

C#

public bool isOdd(int n)
{
    if ((n & 1) == 1)
        return true;
    else
        return false;
}

VB.NET

Public Function IsOdd(ByVal N As Integer) As Boolean
    If (N And 1) = 1 Then
        Return True
    Else
        Return False
    End If
End Function

Contare il numero di setbit in N

Algoritmo Naive

Un altro domanda classicamente posta durante i colloqui di lavoro, consiste nel determinare il numero di bit pari ad 1 nella codifica binaria di un dato numero N. 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. Graficamente, può essere rappresentato come segue. Prendiamo in considerazione il numero 25 e la sua rappresentazione binaria:

Una semplice implementazione di questo algoritmo in C# e VB.NET è la seguente:

C#

public int countSetBitNaive(int n)
{
    int sumSetBit = 0;
    while (n != 0)
    {
        sumSetBit += n & 1;
        n >>= 1;
    }
    return sumSetBit;
}

VB.NET

Function CountSetBitNaive(N As Integer) As Integer
    Dim SumSetBit As Integer = 0
    Do While N <> 0
        SumSetBit += N And 1 
        N >>= 1 
    Loop
    Return SumSetBit
End Function

Algoritmo di Kernighan

Un altro modo per implementare questo algoritmo, velocizzando il procedimento ad un numero di passaggi pari all’effettivo numero di bit pari ad 1, è attraverso l’algoritmo di Kernighan. Questo algoritmo sfrutta la relazione che esiste tra un numero e il precedente, ovvero tra N e (N-1), quando sono codificati in binario. Se infatti si applica l’operazione And su questi due numeri, si ottiene l’azzeramento del primo bit di N a partire da destra che risulta essere pari a 1. In questo modo è possibile fare un loop in cui viene contato semplicemente il numero di volte in cui l’operazione viene eseguita prima che il numero diventi pari a 0. Un’implementazione di questo algoritmo è la seguente:

C#

public int countSetBitKernighan(int n)
{
    int sumSetBit = 0;
    while (n != 0)
    {
        n = n & n-1;
        sumSetBit +=  1;
    }
    return sumSetBit;
}

VB.NET

Function CountSetBitKernighan(N As Integer) As Integer
    Dim SumSetBit As Integer = 0
    Do While N <> 0
        N = N AND N - 1
        SumSetBit +=  1 
    Loop
    Return SumSetBit
End Function

Testare se N è una potenza di 2

Un altro quesito facilmente risolvibile attraverso gli operatori logici quando, N è codificato in binario, è il controllare se N risulta essere una potenza di 2 o meno. Questo può essere rapidamente risolto ricordando che se N è una potenza di 2, la sua codifica in binario sarà uguale ad un primo bit pari a 1 seguito da tanti bit pari a 0 quanto è la potenza di 2. Ad esempio, 16, che è pari a 2^4, sarà rappresentato in binario dal numero 1 0 0 0 0. Per verificare allora se un numero è una potenza di 2 basterà allora verificare che N And (N-1) restituisce subito come risultato 0. Un’implementazione di questo algoritmo in C# e VB.NET è la seguente:

C#

public bool isPowerOf2(int n)
{
    if ((n & n - 1) == 0)
        return true;
    else
        return false;
}

VB.NET

Public Function IsPowerOf2(ByVal N As Integer) As Boolean
    If (N And N - 1) = 0 Then
        Return True
    Else
        Return False
    End If
End Function

Determinare la massima potenza di 2 che divide N

Un ultimo quesito risolto in questo articolo riguarda il trovare la massima potenza di 2 che divide un numero N. Considerando la sua scrittura in binario, è facile notare che essa è esattamente pari al primo bit (partendo da destra) pari ad 1. Basterà, quindi, porre pari a 0 tutti i bit che seguono il primo bit pari ad 1. Per farlo non servirà altro che eseguire l’operazione N And Not (N – 1). Una semplice implementazione di questo algoritmo è la seguente:

C#

public int maxPowerOf2_factor(int n)
{
    return (n & !(n - 1));
}

VB.NET

Public Function MaxPowerOf2_factor(ByVal N As Integer) As Integer
    
    Return (N And Not (N - 1))

End Function