Mustern der gesetzten Bits in einem Byte

Question

Joel erwähnt die Anzahl der gesetzten Bits in einem Byte als Programmier Frage Zählen in seinem Guerrilla-Führer zu interviewen und eine Art und Weise gesprochen Vorteil von Mustern zu nehmen, die in der Lookup-Tabelle auftreten. Ich schrieb einen Artikel über sie eine Weile zurück, nachdem ich das Muster gefunden.

Um es zusammenzufassen:

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  

Die erste Zeile und Spalte sind genau dieselben, und jede Position in dem Gitter kann durch Zugabe von den ersten Werten in dieser Position der Zeile und Spalte berechnet werden. Aus diesem Grunde müssen Sie nur eine Lookup-Tabelle mit 16 Einträgen für eine 8-Bit-Zahl, und können nur die ersten 16 Nummern verwenden. Dann, wenn Sie die gesetzten Bits in der Nummer 243, beispielsweise zählen wollen, würden Sie gerade tun:

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

Das nächste Muster, das ich danach auffiel, war, dass jedes Mal, wenn Sie die Größe des NxN Gitters verdoppeln, könnte jeder Quadrant durch Zugabe von 0, 1, 1 und 2 zu jedem Quadranten berechnet wird jeweils wie folgt:

# 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  

Wiederholen Sie diesen Vorgang zwei weitere Male, und Sie werden das 16x16 Raster von oben, so dass ich dachte, es muss irgendeine Art von Quadtree-Algorithmus, die Sie aus dem Netz zu starten erlauben würde:

0 1
1 2

und eine Anzahl N gegeben, erzeugen im Fluge der Lookup-Tabelle und das Bild die Anzahl von Bits aus. Also meine Frage / Herausforderung ist, können Sie einen Algorithmus herauszufinden, genau das zu tun?

Answer 1

Basierend auf Roberts Code hier , es kann auch ohne die Teilung oder Modul durchgeführt werden, so dass sie mit einer Verschiebung zu ersetzen und einem AND, etwa so:

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 

oder 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
}

Für jede Größe integer, Sie könnten nur eine Schleife durch die Bytes und tun eine schnelle Suche, etwa so:

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

Ich bin mit dieser Antwort zufrieden. Ich wusste, dass etwas komplexer und Quadtree-esque wäre nicht effizient sein, ich dachte nur, es ein ordentliches Gedankenexperiment war.

Answer 2

Dies ist eine dumme Frage! Im ersten Beispiel, in dem Sie die Anzahl der Bits berechnet haben statt 256 eine 16-Eintrag Tabelle verwendet, ist nichts magisch! Alles, was Sie getan haben, ist die Anzahl der Bits in den ersten vier Bits der Bytes (ersten Nibble) und dann in der zweiten knabbert, und fügte hinzu, die beide zusammen gesetzt zählen. x / 16 wird das erste Halbbyte, x% 16 ist das zweite Nibble.

Wenn Sie den Vorgang wiederholen, jetzt haben Sie eine Lookup-Tabelle für zwei Bits und Sie tun es einfach viermal, einmal für jedes Paar. Im Extremfall können Sie fügen Sie einfach alle Bits zusammen one-by-one und Sie erhalten die offensichtliche Antwort.

Der ganze Sinn einer Lookup-Tabelle ist die Zugabe zu vermeiden.

Answer 3

Entschuldigen Sie die späte Post, aber ich habe gerade die Herausforderung an. My $ .02 (Brute-Force)

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