Patrones de bits establecidos en un byte

Question

Joel mencionó contar el número de bits establecidos en un byte como una pregunta de programación en su Guía de guerrilla a Entrevistar , y habló de una forma de aprovechar los patrones que ocurren en la tabla de búsqueda. Escribí un artículo al respecto hace un tiempo después de encontrar el patrón.

Para resumir:

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 primera fila y columna son exactamente iguales, y cada posición en la cuadrícula se puede calcular agregando los primeros valores en la fila y columna de esa posición. Debido a esto, solo necesita una tabla de búsqueda con 16 entradas para un número de 8 bits, y solo puede usar los primeros 16 números. Entonces, si quisiera contar los bits establecidos en el número 243, por ejemplo, simplemente haría:

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

El siguiente patrón que noté después de eso fue que cada vez que duplica el tamaño de la cuadrícula NxN, cada cuadrante se puede calcular agregando 0, 1, 1 y 2 a cada cuadrante, respectivamente, de la siguiente manera:

# 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  

Repita este proceso dos veces más, y obtendrá la cuadrícula de 16x16 desde arriba, así que pensé que debe haber algún tipo de algoritmo quadtree que le permita comenzar desde la cuadrícula:

0 1
1 2

y dado un número N, genere la tabla de búsqueda sobre la marcha y calcule el número de bits. Entonces, mi pregunta / desafío es, ¿puedes encontrar un algoritmo para hacer exactamente eso?

Answer 1

Basado en el código de Robert aquí , incluso se puede hacer sin la división o el módulo, reemplazándolos con un turno y uno Y, así:

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

Para un número entero de cualquier tamaño, puede recorrer los bytes y hacer una búsqueda rápida, así:

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

Estoy satisfecho con esta respuesta. Sabía que algo más complejo y quadtree-esque no sería eficiente, solo pensé que era un experimento mental decente.

Answer 2

¡Esta es una pregunta tonta! ¡En el primer ejemplo donde has calculado el número de bits establecidos usando una tabla de 16 entradas en lugar de 256 no es nada mágico! Todo lo que ha hecho es contar el número de bits establecidos en los primeros cuatro bits del byte (primer mordisco) y luego en el segundo mordisco, sumando los dos. x / 16 es el primer mordisco, x% 16 es el segundo mordisco.

Si repite el proceso, ahora tiene una tabla de búsqueda para dos bits y solo lo hace cuatro veces, una para cada par. En el extremo, puede agregar todos los bits uno por uno y obtener la respuesta obvia.

El objetivo de una tabla de búsqueda es evitar la adición.

Answer 3

Disculpe la publicación tardía, pero acabo de encontrar el desafío. My $ .02 (fuerza 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