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

In informatica e programmazione, un operatore è un simbolo che specifica quale legge applicare a uno o più operandi, per generare un risultato. Gli operatori possono essere classificati in base al numero di operandi che accettano, ovvero in base al numero di dati su cui lavorano, o in base alle operazioni che svolgono e ad i risultati che forniscono. La prima divisione degli operatori presenti in C# e VB.NET in base al numero di operandi che accettano è la seguente:

• operatori unari (o unary) sono operatori che richiedono un solo operando e sono ad esempio l’operatore not in VB.NET e !in C#;
• operatori binari (o binary) lavorano su due operandi, come ad esempio gli operatori aritmetici più comuni o quelli di assegnamento;
• operatori ternari (o ternary) lavorano su tre operandi; sono operatori non molto comuni, uno dei rari esempi è l’operatore condizionale, usato in programmazione, rappresentato in C# attraverso il simbolo “?” e in VB.NET attraverso la funzione If(). Il suo funzionamento è relativamente semplice. In C# la sintassi A?B:C significa che se A risulta essere vero allora il programma restituisce B, altrimenti viene restituito C. Analogamente, questa operazione può essere compiute in VB.NET attraverso la sintassi If(A,B,C).

Una suddivisione per funzionalità degli operatori è la seguente:

• aritmetici: sono +, -, *, /, %, \ e lavorano su due operandi;
• incremento e decremento: sono unari, rispettivamente aumentano o diminuiscono di uno l’unico operando che prendono;
• logici booleni:  lavorano su dati booleani, ovvero variabili che possono assumere solo i valori vero e falso e servono a formulare condizioni composte; ne sono un esempio in NOT, AND, OR, XOR VB.NET, o gli equivalenti in C# !, &, |, ^;
• bitwise: consentono di manipolare direttamente i bit di un valore e sono uguali agli operatori logici, fatta eccezione per !, che viene tradotto con ~;
• relazione: sono operatori binary che consentono di controllare la relazione tra due operandi, sono <>, =, <, >, <= , >=, is, isnot in VB.NET e C#, fatta eccezione per i primi due dove in C# sono tradotti con !=, ==;
• concatenazione di stringhe: rispettivamente & e + in VB.NET e C#, servono per la concatenazione di stringhe;
• condizionali In VB.NET si utilizzano ANDALSO, ORELSE, in C# sono tradotti con &&, ||. Questi operatori differiscono dai logici perché quest’ultimi valutano i due termini operandi in ogni caso, mentre gli operatori condizionali valutano il secondo operando solo se strettamente necessario. Questo procedimento è detto short circuiting.

I tipi numerici a “precisione arbitraria” (conosciuti anche come interi a “precisione infinita” o bignum), permettono la rappresentazione del numero attraverso uno spazio mutevole di memoria, aumentando enormemente il range di rappresentazione del numero. L’unico limite si pone, infatti, per la finitezza della memoria del computer. Tuttavia, con 8 KB di memoria, si può arrivare a rappresentare numeri di 2466 cifre.

Alcuni linguaggi supportano direttamente i numeri a precisione arbitraria. In altri linguaggi è invece necessario importare delle apposite librerie. La libreria System.Numerics contiene una classe BigInteger i cui oggetti possono rappresentare numeri interi di lunghezza arbitraria. Questi oggetti non utilizzare i classici operatori aritmetici ( + * – / =), ma è necessario utilizzare i metodi forniti dalla classe stessa, che sono: add, multiply, subtract, equals. Per poter inizializzare i numeri BigInteger, è necessario utilizzare un metodo Parse per poter assegnare l’intero arbitrario come stringa. Questo è necessario poiché altrimenti non sarebbe possibile rappresentare numeri di queste dimensioni.

Il fattoriale di un numero n, indicato con la simbologia n!, rappresenta il prodotto di tutti gli interi da 1 fino al numero n compresi, ovvero:

Il calcolo del fattoriale seguendo la formula canonica può rivelarsi essere molto lungo e molto esigente, dal punto di vista del costo computazionale. Tuttavia esistono diversi algoritmi che permettono il calcolo del fattoriale in un minor lasso di tempo. I principali sono:

• SpliRecursive: è l’algoritmo più rapido che non utilizza la fattorizzazione in primi ed è relativamente semplice da implementare;
• PrimeSwing: è l’algoritmo conosciuto asintoticamente più veloce per calcolare n!; si basa sul concetto di “Swing Numbers”, calcolando il fattoriale tramite la scomposizione in fattori primi;
• Poor Man’s: questo algoritmo non utilizza nessuna libreria Big-Integer, può essere facilmente implementato su qualsiasi computer ed è rapido fino a 10000 fattoriale.
• ParallelPrimeSwing: corrisponde all’algoritmo PrimeSwing con prestazioni migliorate grazie a metodi di programmazione concorrenti e sfruttando così processori multipli.

In programmazione la gestione degli errori è il processo di risposta all’occorrenza di exceptions, che sono condizioni anomale o speciali che richiedono una gestione speciale. Queste eccezioni (o errori) vengono “lanciate” automaticamente dal compilatore quando si imbatte in problemi che interrompono la normale esecuzione del programma (come, ad esempio, overflow). In poche parole, quando si verifica un imprevisto, il metodo attivo “lancia” (throw) un’eccezione che viene passata al metodo chiamante. Il metodo attivo termina quindi l’esecuzione. Per default, un metodo che riceve un’eccezione termina l’esecuzione e passa l’eccezione al metodo chiamante. Quando l’eccezione raggiunge il metodo main (ovvero il metodo principale), l’esecuzione del programma termina stampando un opportuno messaggio di errore.

Tuttavia, è possibile gestire gli errori in maniera tale da non interrompere il programma e gestendo anche la stampa del messaggio di errore, lasciando al programmatore la possibilità di gestirlo nella maniera più consona. La struttura Try, Catch serve esattamente a questo. Si compone da due blocchi di comandi, più un terzo non obbligatorio, che hanno le seguenti funzioni:

• il blocco Try contiene le istruzioni da eseguire, che potrebbero generare eccezioni e che si vuole controllare;
• il blocco Catch contiene la gestione degli errori che potrebbero essere generati durante l’esecuzione del Try (è possibile aggiungere più blocchi Catch per gestire separatamente le diverse tipologie di eccezioni che il Try può generare);
• il blocco Finally può, facoltativamente, essere messo alla fine e comprende il blocco di istruzioni da eseguire indipendentemente dall’esito delle istruzioni contenute nel blocco Try.

La sintassi del Try, Catch per quanto riguarda C# e VB.NET è la seguente:

C#

try
{
    <tryStatements>
}
catch(Exception)
{
    <catchStatements>
}
cathch...
finally
{
    <finallyStatements>
}

VB.NET

Try
    [ tryStatements ]
    [ Exit Try ]
[ Catch [ exception [ As type ] ] [ When expression ]
    [ catchStatements ]
    [ Exit Try ] ]
[ Catch ... ]
[ Finally
    [ finallyStatements ] ]
End Try

Il blocco Try, Catch funziona abbastanza linearmente; vengono eseguite le istruzioni contenute nel Try. Se l’esecuzione procede senza aver generato nessun errore, vengono eseguite le istruzioni presenti nel Finally (se presente) e il programma prosegue con la prima istruzione dopo il blocco Try, Catch. Se invece vengono generate delle eccezioni durante il Try, l’esecuzione termina alla prima istruzione che genera errore(le istruzioni successive a quella incriminata non vengono quindi eseguite) e viene eseguita la gestione presente nel blocco Catch relativo al tipo di errore generato (può anche darsi che il Catch gestisca qualsiasi generico errore, non è necessario specificare un Catch per ogni errore che potrebbe essere generato). Infine vengono comunque eseguite le istruzioni nel Finally.

Si può gestire un’eccezione anche in maniera più “pigra”, inserendo nella definizione del metodo una “throw exception“. Questo comando in sostanza significa che il metodo appena eseguito potrebbe generare una eccezione e che il metodo chiamante deve occuparsi della sua gestione.

In C# e VB.NET il comportamento delle eccezioni non gestite è leggermente differente:

• in C# l’ultimo metodo chiamante che non comprende il comando “throw exception” deve gestire l’eccezione con un blocco Try, Catch;
• in VB.NET: è presente un gestore di eventi (“Eccezione non gestita”) che consente, , di intercettare l’eccezione in cima alla pila e di definire la sua gestione.