Os padrões de bits definidos em um byte
-
20-08-2019 - |
Pergunta
Joel mencionado contar o número de bits definidos em um byte como uma questão de programação em seu Guerrilla Guia para Entrevistar , e falou de uma maneira de tirar proveito de padrões que ocorrem na tabela de pesquisa. Eu escrevi um artigo sobre isso algum tempo atrás depois que eu encontrei o padrão.
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
A primeira linha e coluna são exatamente o mesmo, e cada posição na grade pode ser calculado somando os primeiros valores na linha e coluna dessa posição. Devido a isso, você só precisa de uma tabela de pesquisa com 16 entradas para um número de 8 bits, e pode usar apenas os primeiros 16 números. Então, se você quiser contar os bits definidos no número 243, por exemplo, você tinha acabado de fazer:
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
O próximo padrão notei depois disso foi que cada vez que você dobrar o tamanho da grade NxN, cada quadrante pode ser calculado adicionando 0, 1, 1 e 2 para cada quadrante, respectivamente, assim:
# 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 esse processo mais duas vezes, e você vai ter a grade de 16x16 de cima, então eu percebi que deve haver algum tipo de quadtree algoritmo que lhe permitiria iniciar a partir da rede:
0 1
1 2
e dado um número N, gerar a tabela de consulta na mosca e descobrir o número de bits. Então, minha pergunta / desafio é, você pode descobrir um algoritmo para fazer isso?
Solução 2
Com base no código de Robert aqui , ele pode até mesmo ser feito sem a divisão ou módulo, substituindo-os por um turno e um e, assim:
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 em 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 qualquer inteiro tamanho, você poderia simplesmente percorrer os bytes e fazer uma pesquisa rápida, assim:
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
Estou satisfeito com esta resposta. Eu sabia que algo mais complexo e quadtree-esque não seria eficiente, eu apenas pensei que era um experimento de pensamento decente.
Outras dicas
Esta é uma pergunta boba! No primeiro exemplo onde você calculado o número de bits definidos usando uma tabela de 16 entrada em vez de 256 não é nada mágico! Tudo que você fez é contar o número de bits definidos nos quatro primeiros bits do byte (primeira mordidela) e, em seguida, na segunda mordidela, adicionando os dois juntos. x / 16 é o primeiro mordidela, x% 16 é o segundo nibble.
Se você repetir o processo, agora você tem uma tabela de pesquisa para dois bits e você apenas fazê-lo quatro vezes, uma para cada par. Em casos extremos, você pode simplesmente adicionar todos os pedaços juntos, um por um e você terá a resposta óbvia.
O ponto inteiro de uma tabela de pesquisa é evitar a adição.
Com licença final do post, mas eu só descobri o desafio. Minha US $ .02 (força 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