Página 1 de 2

Hamming Weight

MensagemEnviado: Sábado Jan 29, 2011 3:11 pm
por 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

Re: Hamming Weight

MensagemEnviado: Domingo Jan 30, 2011 10:53 pm
por 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

Re: Hamming Weight

MensagemEnviado: Domingo Jan 30, 2011 11:24 pm
por 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 :P No entanto, uma maneira possível de fazer isso, também envolve ciclos while, por isso, estás no bom caminho!!

Re: Hamming Weight

MensagemEnviado: Segunda Jan 31, 2011 2:52 pm
por 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 é?

Re: Hamming Weight

MensagemEnviado: Segunda Jan 31, 2011 10:27 pm
por Bruno Oliveira
Sim, exactamente, é essa a quantidade pedida!

Re: Hamming Weight

MensagemEnviado: Segunda Jan 31, 2011 11:06 pm
por 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.

Re: Hamming Weight

MensagemEnviado: Terça Fev 01, 2011 12:25 pm
por 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 :P

Re: Hamming Weight

MensagemEnviado: Quarta Fev 02, 2011 10:33 pm
por jap
francisco_machado Escreveu: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... :lol:

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                 


:wink:

Re: Hamming Weight

MensagemEnviado: Quinta Fev 03, 2011 2:35 pm
por 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


:)

Re: Hamming Weight

MensagemEnviado: Quinta Fev 03, 2011 2:55 pm
por Bruno Oliveira
:yes

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.

Re: Hamming Weight

MensagemEnviado: Quinta Fev 03, 2011 5:02 pm
por 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

Re: Hamming Weight

MensagemEnviado: Quinta Fev 03, 2011 5:44 pm
por hexphreak
Consigo fazer melhor do que isso se o peso de Hamming for pequeno (ou grande) :P

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

Re: Hamming Weight

MensagemEnviado: Quinta Fev 03, 2011 11:04 pm
por 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 &?

Re: Hamming Weight

MensagemEnviado: Quinta Fev 03, 2011 11:11 pm
por jap
francisco_machado Escreveu:(...)
Agora eu tenho dúvida, será que é possível explicarem esses operadores o >>= e o &?


Isso é X-rated Python! :lol:

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! :wink:

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

Re: Hamming Weight

MensagemEnviado: Quinta Fev 03, 2011 11:52 pm
por 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