Algoritmi classici di manipolazione dei bit
Le grandi società, come Google e Amazon, fanno alcune domande classiche durante i colloqui di lavoro che riguardano problemi risolvibili elegantemente mediante la manipolazione dei bit e operatori bitwise. in questo articolo discuteremo proprio di queste domande:
- Determinare il valore LSB (Less Significative Bit) di un numero qualunque N. Il valore LSB è il valore che assume il bit all'estrema destra. Essendo un linguaggio macchina abbiamo un linguaggio binario quindi l'ultimo valore a destra potrà essere 0 oppure 1; riuscendo a stabilire questo valore sarà possibile definire se N è pari o disperi. Per determinare questo valore si utilizza l'operatore logico 'AND' in VB.net mentre in c# si utilizza '&'.
Si esegue la seguente operazione:N AND 1,In questo caso infatti l’operazione avrebbe come risultato 1 se anche l’ultimo bit del nostro numero N vale 1 (quindi il numero è dispari), mentre si otterrebbe 0 se l’ultimo bit di N vale 0 (quindi N è pari).
Di seguito si ha un esempio del codice VB.NET :
Private Function IsEven(ByVal N As Integer) As Boolean
If (N And 1) = 0 Then
Return True
Else
Return False
End If
End Function
- Risolvere il problema del conteggio del numero di bit in un numero N qualsiasi. Si deve studiare il valore del bit più a destra e poi shiftare di una posizione verso destra tutti i bit , eliminando così il bit precedentemente visionato, fino a quando non si arriverà al numero 0. Per poter studiare l’ultimo bit basterà utilizzare l’operazione vista in precedenza. Questo algoritmo, che si può definire “naive”, esegue n iterazioni, dove n è il numero di bit totali che compongono N.
Function CountsetBit_Naive(N As Integer) As Integer
Dim contatoresetbit As Integer = 0
Do While N <> 0 ' finche N diverso da zero
contatoresetbit += (N And 1)
N >>= 1 'shifto di 1 verso destra
Loop
Return contatoresetbit
End Function
Un algoritmo sicuramente più efficiente è l’algoritmo di Kernighan poichè permette di implementare la stessa richiesta in un numero di passaggi inferiore, uguale al numero effettivo di bit pari a
1.. Questo algoritmo sfrutta la relazione che c’è tra N e
(N-1); infatti l’operazione N And (N-1) causa l’azzeramento del primo bit di N uguale a 1 da destra. Inserendo questa relazione in un loop sarà possibile infatti azzerare tutti i bit pari a 1 fino ad arrivare al numero 0.
Function CountsetBit_Kernighan(N As Integer) As Integer
Dim contatoresetbit As Integer = 0
Do While N <> 0 ' finche N diverso da zero
N = N And (N - 1)
contatoresetbit += 1
Loop
Return contatoresetbit
End Function
3. testare se un qualsiasi numero n sia o meno potenza di 2.
L'operazione
N And (N-1) può essere utilizzata anche per testare se N è una potenza di 2: Se l’operazione N And (N-1) dà subito 0 vuol dire quindi che N è una potenza di 2. Questo risultato si ha in virtù del fatto che i numeri che sono potenze di 2 sono rappresentati in binario da una cifra 1 seguita da tante cifre 0 quanto è la potenza di 2.
Private Function IsPowerOf2(ByVal N As Integer) As Boolean
If (N And (N - 1)) = 0 Then
Return True
Else
Return False
End If
End Function
4. trovare la più grande potenza di 2 che divide un numero qualunque N.
L’obiettivo è trovare la massima potenza di 2 che divide un numero intero N. Analizzando la scrittura di un generico numero N in linguaggio binario, si può facilmente notare che la massima potenza ricercata risulta essere proprio quella corrispondente alla posizione del bit uguale a 1 più a destra. Bisogna dunque cercare il primo bit pari a
1 da destra e spianare a 0 tutte le cifre che si trovano alla sua sinistra. Per spianare questi bit, viene in aiuto la relazione tra N e N-1, negando quest’ultimo operando tramite l’operatore Not.
Private Function MaxPowerof2_Factor(ByVal N As Integer) As Boolean
Return N And Not (N - 1)
End Function
Commenti
Posta un commento