Hamming Weight

[Bruno Oliveira]

Como os novos quarkianos já devem ter tido uma lição de Python por esta altura, aqui fica mais um exercicio de treino pitónico!!!

Define-se peso de Hamming (espero ter traduzido bem!) de uma bitstring como o número de set bits (1-bits) na string.
Assim, o peso de Hamming do número 23, é 4, uma vez que quando escrito na base 2, esse número é 10111.

A vossa tarefa é escreverem um programa, que calcule o peso de Hamming de um número.

PS: Este conceito, o de peso de Hamming, é usado em criptografia, códigos correctores de erros, entre outros tópicos de computação; consta até que há quem o use como interview question.

Bruno

[francisco_machado]

Aqui está o que penso ser uma solução do problema:

Código: Seleccionar Todos

a = input()                 #O valor a considerar
n=0
finished = False            #Variável para acabar o loop quando se quer

while not finished:         #O loop

    n = n+1                 #O incremento do n
   
    if 2**n >= a:           #Queremos encontrar o menor n que 2^n seja maior ou igual
        finished = True     #ao valor que colocámos, sendo este n o nº de bits donúmero
       
print n-1                   #Como se quer o n-1, retorna-se o n-1


[Bruno Oliveira]

O teu programa está certo, mas não faz bem o que eu pedi!

EDIT: Pedi apenas, o número de 1-bits da bitstring, não o número total de bits No entanto, uma maneira possível de fazer isso, também envolve ciclos while, por isso, estás no bom caminho!!

[francisco_machado]

Então li mal, desculpa.

O que é pedido então é o números de 1 que a representação binária do número tem não é?

[Bruno Oliveira]

Sim, exactamente, é essa a quantidade pedida!

[francisco_machado]

Nesse caso fica aqui a minha solução

Código: Seleccionar Todos

a = input()                 #o valor a considerar
n=0
finished = False            #variável para acabar o loop quando se quer

while not finished:         #o loop
    n = n+1                 #o incremento do n
    if 2**n >= a:           #queremos encontrar o menor n que 2^n seja maior ou igual
        finished = True     #ao valor que colocámos, sendo este n o nº de bits donúmero
       
finished = False            #Como se quer o n-1, retorna-se o n-1

total=0                     #Nº total de 1's

for i in range(n-1,-1,-1):  #Ínicio do loop para contar, começa-se no n-1, porque o n-ésimo
                            # bit corresponde a 2**(n-1) e mete-se o -1, para chegar a 2**0,
                            #visto que i nunca chega a este valor final
                           
    if 2**(i) <= a:         #Se 2**i for menor que o valor, temos que esse bit será 1
        a -= 2**(i)         #Retira-se 2**i para garantir que não temos falsos positivos
        total += 1          #Adiciona-se mais 1 ao total
   
         
print total                 #Faz-se o display do total



Tentei explicar o código com os comentários, se alguém tiver alguma dúvida é só perguntar.

[hexphreak]

Em relação aos comentários, não precisas de dizer coisas como "o loop", "o incremento do n" ou "Faz-se o display do total", porque são perfeitamente óbvias para quem lê o código. A ideia dos comentários é clarificar aspectos mais obscuros do código, as passagens "tricky" por assim dizer, e não indicar o propósito de cada linha.

Idealmente, o código nem sequer precisaria de comentários, porque os algoritmos e as estruturas de dados devem estar explicados à parte e o código deve ser self-commenting, i.e. deve ser claro para quem conhece o algoritmo e o propósito e as interfaces das estruturas. Claro, para programas com um tamanho desta ordem de grandeza basta um comentário inicial a explicar o algoritmo, se necessário ou esclarecedor, não de documentação extensiva

[jap]

Nesse caso fica aqui a minha solução

Código: Seleccionar Todos

a = input()                 #o valor a considerar
n=0
finished = False            #variável para acabar o loop quando se quer

while not finished:         #o loop
    n = n+1                 #o incremento do n
    if 2**n >= a:           #queremos encontrar o menor n que 2^n seja maior ou igual
        finished = True     #ao valor que colocámos, sendo este n o nº de bits donúmero
       
finished = False            #Como se quer o n-1, retorna-se o n-1

total=0                     #Nº total de 1's

for i in range(n-1,-1,-1):  #Ínicio do loop para contar, começa-se no n-1, porque o n-ésimo
                            # bit corresponde a 2**(n-1) e mete-se o -1, para chegar a 2**0,
                            #visto que i nunca chega a este valor final
                           
    if 2**(i) <= a:         #Se 2**i for menor que o valor, temos que esse bit será 1
        a -= 2**(i)         #Retira-se 2**i para garantir que não temos falsos positivos
        total += 1          #Adiciona-se mais 1 ao total
   
         
print total                 #Faz-se o display do total



Tentei explicar o código com os comentários, se alguém tiver alguma dúvida é só perguntar.

Francisco,

Obrigado pelo teu código.!

Estás a prender a programar em Python, ou já sabias programar noutra linguagem de programação?
É que o teu código tem um estilo pouco pitónico...

Eu explico.

Em vez de

Código: Seleccionar Todos

while not finished:         #o loop
    n = n+1                 #o incremento do n
    if 2**n >= a:           #queremos encontrar o menor n que 2^n seja maior ou igual
        finished = True     #ao valor que colocámos, sendo este n o nº de bits donúmero



a pitonice idiomática seria:

Código: Seleccionar Todos

while 1:       
    n = n+1                 
    if 2**n >= a: break         


ou, melhor ainda:

Código: Seleccionar Todos

while 2**n < a:
      n + = 1                 


[Tharis]

Já que se deixou alguns novos participantes responder, deixo aqui a forma mais simples:

Código: Seleccionar Todos

>>> print bin(23).count('1')
4

[Bruno Oliveira]

Como eu disse, por este conceito ser tão importante, há inclusivé, como o Tharis aqui postou, um método de string, que nos devolve o número de 0s ou de 1s, na bitstring.

Além do Python, muitas outras linguagens de programação, têm este método implementado, como C++, Java e Lisp.

E retirado da wikipedia, só por curiosidade:

Cray supercomputers early on featured a population count machine instruction, rumoured to have been specifically requested by the U.S. government National Security Agency for cryptanalysis applications.

[Tharis]

Já agora, uma implementação de um algoritmo em poucas linhas (e comentário encontra-se código equivalente mais simples para quem não conhece bitops):

Código: Seleccionar Todos

n = 23; t = 0
while n:
    t += n&1    # t += n%2
    n >>= 1    # n /= 2
print t


[hexphreak]

Consigo fazer melhor do que isso se o peso de Hamming for pequeno (ou grande)

Código: Seleccionar Todos

t = 0
while n:
    t += 1
    n = n & (n-1)
print t


Claro que, sendo Python, ninguém está muito preocupado com a eficiência do código...

[francisco_machado]

Obrigado hexphreak pelo remarco.
Eu raramente mostro o meu código a outras pessoas e raramente ponho comentários, portanto ainda não tenho bem a noção do que devo ou não pôr em comentários, mas como era para a comunidade pensei em demonstrar o meu raciocínio o melhor possível.

Agora eu tenho dúvida, será que é possível explicarem esses operadores o >>= e o &?

[jap]

(...)
Agora eu tenho dúvida, será que é possível explicarem esses operadores o >>= e o &?

Isso é X-rated Python!

Os operadores binários >> e & correspondem à operação de deslocamento de bits para a direita (n >>1 desloca os bits de n uma unidade para a direita, o que corresponde, se n for um inteiro, à divisão por 2) e de operação lógica (bitwise) AND (a & b é o equivalente de a AND b, bit a bit).

Se isto te parece chinês, don't worry!

Só os engenheiros electrotécnicos e os C-hackers é que usam este tipo de código obscuro.

[Tharis]

Só para completar o que o Prof. jap disse com alguns exemplos:

Código: Seleccionar Todos

>>> bin(23)
'0b10111'
>>> bin(23>>1)
'0b1011'


O que acontece quando aplicas >>1 é empurrares os dígitos uma casa para a direita, sendo o último dígito "descartado". Isto equivale claro a uma divisão por 2 no caso de n inteiro.

Código: Seleccionar Todos

>>> bin(117)
'0b1110101'
>>> bin(104)
'0b1101000'
>>> bin(117&104)
'0b1100000'


O operador & aplica a condição AND aos pares de bits na mesma posição em cada número. As posições em que ambos os números têm 1 ficam com 1, todas as outras ficam com 0s.

1110101
1101000
-------
1100000