Modelli di bit impostati in un byte

Question

Joel ha menzionato il conteggio del numero di bit impostati in un byte come una domanda di programmazione nel suo Guida alla guerriglia per le interviste, e ha parlato di un modo per sfruttare i modelli che si verificano nella tabella di ricerca.Ho scritto un articolo a riguardo qualche tempo fa dopo aver trovato lo schema.

Riassumere:

Number of bits set in a byte in 16x16
0   1   1   2   1   2   2   3   1   2   2   3   2   3   3   4  
1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
4   5   5   6   5   6   6   7   5   6   6   7   6   7   7   8  

La prima riga e colonna sono esattamente le stesse e ciascuna posizione nella griglia può essere calcolata aggiungendo i primi valori nella riga e nella colonna di quella posizione.Per questo motivo, hai solo bisogno di una tabella di ricerca con 16 voci per un numero a 8 bit e puoi utilizzare solo i primi 16 numeri.Quindi, se volessi contare i bit impostati nel numero 243, ad esempio, dovresti semplicemente fare:

a = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
x = 243 / 16 => 15 # (int)
y = 243 % 16 => 3

a[x] + a[y] => 6

# Are there six bits set in the number 243?
243 = 11110011 # yep

Lo schema successivo che ho notato è che ogni volta che raddoppi la dimensione della griglia NxN, ogni quadrante può essere calcolato aggiungendo rispettivamente 0, 1, 1 e 2 a ciascun quadrante, in questo modo:

# Make a 4x4 grid on the paper, and fill in the upper left quadrant with the values of the 2x2 grid.  
# For each quadrant, add the value from that same quadrant in the 2x2 grid to the array.  

# Upper left quad add 0 to each number from 2x2  
0   1   *   *  
1   2   *   *  
*   *   *   *  
*   *   *   *  

# Upper right quad add 1 to each number from 2×2  
0   1   1   2  
1   2   2   3  
*   *   *   *  
*   *   *   *  

# Lower left quad add 1 to each number from 2×2  
0   1   1   2  
1   2   2   3  
1   2   *   *  
2   3   *   *  

# Lower right quad add 2 to each number from 2×2  
0   1   1   2  
1   2   2   3  
1   2   2   3  
2   3   3   4  

Ripeti questo processo altre due volte e otterrai la griglia 16x16 dall'alto, quindi ho pensato che ci dovesse essere una sorta di algoritmo quadtree che ti permettesse di iniziare dalla griglia:

0 1
1 2

e dato un numero N, genera al volo la tabella di ricerca e calcola il numero di bit.Quindi la mia domanda/sfida è: riesci a trovare un algoritmo per fare proprio questo?

Answer 1

Basato sul codice di Robert qui , può anche essere fatto senza la divisione o il modulo, sostituendoli con uno spostamento e uno E, in questo modo:

a = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
x = 243 >> 4 # 15 (same as dividing by 16)
y = 243 & 0x0f # 3 ( same as modding by 16)

result = a[x] + a[y] # 6 bits set 

O in C:

const unsigned char oneBits[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};

unsigned char CountOnes(unsigned char x)
{
    unsigned char results;
    results = oneBits[x&0x0f];
    results += oneBits[x>>4];
    return results
}

Per numeri interi di qualsiasi dimensione, puoi semplicemente scorrere i byte e fare una rapida ricerca, in questo modo:

def bits(n)
    a = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
    a[n >> 4] + a[n & 0x0f]
end

def setBits(n)
   total = 0
   while(n > 0)
       total += bits(n&0xff)
       n >>= 8
   end
   total
end

setBits(6432132132165432132132165436265465465653213213265465) # 78 bits set

Sono soddisfatto di questa risposta. Sapevo che qualcosa di più complesso e quadrifoglio non sarebbe stato efficiente, ho solo pensato che fosse un esperimento di pensiero decente.

Answer 2

Questa è una domanda stupida!Nel primo esempio in cui hai calcolato il numero di bit impostati utilizzando una tabella a 16 voci invece di 256 non c'è niente di magico!Tutto quello che hai fatto è contare il numero di bit impostati nei primi quattro bit del byte (primo nibble) e poi nel secondo nibble, sommando i due insieme.x/16 è il primo bocconcino, x%16 è il secondo bocconcino.

Se ripeti il ​​processo, ora hai una tabella di ricerca per due bit e devi farlo semplicemente quattro volte, una per ogni coppia.In casi estremi, puoi semplicemente sommare tutti i pezzi uno per uno e otterrai la risposta ovvia.

Lo scopo principale di una tabella di ricerca è evitare l'addizione.

Answer 3

Scusa il post in ritardo, ma ho appena trovato la sfida. I miei $ 0,02 (forza bruta)

Private Sub Button1_Click(ByVal sender As System.Object, _
                          ByVal e As System.EventArgs) Handles Button1.Click

    For x As Integer = 0 To 255
        Debug.WriteLine(bitsOn2(CByte(x)) & " " & Convert.ToString(x, 2).PadLeft(8, "0"c))
    Next

End Sub

Private Function bitsOn(ByVal aByte As Byte) As Integer
    Dim aBit As Byte = 1
    For z As Integer = 0 To 7
        If (aByte >> z And aBit) = aBit Then bitsOn += 1
    Next
End Function

Dim aDict As New Dictionary(Of Integer, Integer)
Private Function bitsOn2(ByVal aByte As Byte) As Integer
    If aDict.Count = 0 Then 'init dictionary
        For x As Integer = 0 To 255
            aDict.Add(x, bitsOn(CByte(x)))
        Next
    End If
    Return aDict(aByte)
End Function