Hamming Weight

Secção dedicada à linguagem de programação favorita dos quarkianos: Python!

Hamming Weight

Mensagempor Bruno Oliveira em Sábado Jan 29, 2011 3:11 pm

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
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Hamming Weight

Mensagempor francisco_machado em Domingo Jan 30, 2011 10:53 pm

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
francisco_machado
gluão
gluão
 
Mensagens: 27
Registado: Sexta Fev 26, 2010 8:28 pm

Re: Hamming Weight

Mensagempor Bruno Oliveira em Domingo Jan 30, 2011 11:24 pm

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!!
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Hamming Weight

Mensagempor francisco_machado em Segunda Jan 31, 2011 2:52 pm

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 é?
francisco_machado
gluão
gluão
 
Mensagens: 27
Registado: Sexta Fev 26, 2010 8:28 pm

Re: Hamming Weight

Mensagempor Bruno Oliveira em Segunda Jan 31, 2011 10:27 pm

Sim, exactamente, é essa a quantidade pedida!
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Hamming Weight

Mensagempor francisco_machado em Segunda Jan 31, 2011 11:06 pm

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.
última vez editado por francisco_machado s Terça Fev 01, 2011 1:31 pm, editado 1 vez no total
francisco_machado
gluão
gluão
 
Mensagens: 27
Registado: Sexta Fev 26, 2010 8:28 pm

Re: Hamming Weight

Mensagempor hexphreak em Terça Fev 01, 2011 12:25 pm

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
Avatar do utilizador
hexphreak
top-Quark!
top-Quark!
 
Mensagens: 1959
Registado: Segunda Nov 05, 2007 8:52 pm
Localização: Maia/Porto

Re: Hamming Weight

Mensagempor jap em Quarta Fev 02, 2011 10:33 pm

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:
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Hamming Weight

Mensagempor Tharis em Quinta Fev 03, 2011 2:35 pm

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

Código: Seleccionar Todos
>>> print bin(23).count('1')
4


:)
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Hamming Weight

Mensagempor Bruno Oliveira em Quinta Fev 03, 2011 2:55 pm

: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.
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Hamming Weight

Mensagempor Tharis em Quinta Fev 03, 2011 5:02 pm

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
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Hamming Weight

Mensagempor hexphreak em Quinta Fev 03, 2011 5:44 pm

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...
Avatar do utilizador
hexphreak
top-Quark!
top-Quark!
 
Mensagens: 1959
Registado: Segunda Nov 05, 2007 8:52 pm
Localização: Maia/Porto

Re: Hamming Weight

Mensagempor francisco_machado em Quinta Fev 03, 2011 11:04 pm

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 &?
francisco_machado
gluão
gluão
 
Mensagens: 27
Registado: Sexta Fev 26, 2010 8:28 pm

Re: Hamming Weight

Mensagempor jap em Quinta Fev 03, 2011 11:11 pm

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:
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Hamming Weight

Mensagempor Tharis em Quinta Fev 03, 2011 11:52 pm

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
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Próximo

Voltar para Pitónica

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 3 visitantes

cron