Modèles de bits définis dans un octet

Question

Joel a mentionné le comptage du nombre de bits définis dans un octet en tant que question de programmation dans son Guerrilla Guide. à interviewer , et a parlé d'un moyen de tirer parti des caractéristiques de la table de consultation. J'ai écrit un article à ce sujet il y a quelque temps, après avoir trouvé le motif.

Pour résumer:

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 première ligne et la première colonne sont identiques, et chaque position dans la grille peut être calculée en ajoutant les premières valeurs de la ligne et de la colonne de cette position. Pour cette raison, vous n'avez besoin que d'une table de correspondance avec 16 entrées pour un nombre de 8 bits et vous pouvez simplement utiliser les 16 premiers chiffres. Ensuite, si vous voulez compter les bits définis dans le nombre 243, par exemple, il vous suffira de faire:

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

Le motif suivant que j’ai remarqué par la suite était que chaque fois que vous doubliez la taille de la grille NxN, chaque quadrant pouvait être calculé en ajoutant respectivement 0, 1, 1 et 2 à chaque quadrant, comme suit:

# 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  

Répétez ce processus deux fois de plus, et vous obtiendrez la grille 16x16 d'en haut. J'ai donc pensé qu'il devait exister une sorte d'algorithme à quatre arbres qui vous permettrait de démarrer à partir de la grille:

0 1
1 2

et à partir du nombre N, générez la table de consultation à la volée et calculez le nombre de bits. Ma question / défi est donc, pouvez-vous trouver un algorithme pour faire exactement cela?

Answer 1

Basé sur le code de Robert ici , cela peut même être fait sans division ni module, en les remplaçant par un quart de travail et un AND, comme suit:

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 

Ou en 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
}

Pour tout entier de taille, vous pouvez simplement parcourir les octets et effectuer une recherche rapide, comme suit:

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

Je suis satisfait de cette réponse. Je savais que quelque chose de plus complexe et de quadtree-esque ne serait pas efficace, je pensais juste que c'était une expérience de pensée décente.

Answer 2

C'est une question idiote! Dans le premier exemple où vous avez calculé le nombre de bits défini en utilisant un tableau à 16 entrées au lieu de 256, rien de magique! Tout ce que vous avez fait est de compter le nombre de bits définis dans les quatre premiers bits de l'octet (premier quartet), puis dans le deuxième quartet, en additionnant les deux ensemble. x / 16 est le premier quartet, x% 16 est le deuxième quartet.

Si vous répétez le processus, vous avez maintenant une table de correspondance pour deux bits et vous ne le faites que quatre fois, une fois pour chaque paire. À l'extrême, vous pouvez simplement additionner tous les éléments un par un et obtenir la réponse évidente.

L'intérêt d'une table de correspondance est d'éviter l'ajout.

Answer 3

Excusez le dernier message, mais je viens de trouver le défi. Mon .02 (force brute)

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