Como posso verificar Hamming Peso sem converter para binário?

Question

Como posso obter o número de "1" s na representação binária de um número sem realmente convertendo e contagem?

por exemplo.

  def number_of_ones(n):
      # do something
      # I want to MAKE this FASTER (computationally less complex).
      c = 0
      while n:
        c += n%2
        n /= 2
      return c


>>> number_of_ones(5)
    2
>>> number_of_ones(4)
    1

Answer 1

IMO, uma boa abordagem seria a utilização de uma tabela look-up - criar um dicionário que converte bytes para o número de 1s (você pode usar o código que você postou para gerá-la, ele só precisa ser executado uma vez), e Em seguida, use algo como isto:

def number_of_ones(n):
    sum = 0
    while n != 0:
        sum += lookup_table[n & 0xff]
        n >>= 8
    return sum

Eu acredito que este é um bom trade-off entre o espaço eo tempo em execução.

Answer 2

Eu não sou um programador python, mas espero que seja o suficiente para você seguir.

c = 0
while n:
    c += 1
    n &= n - 1

return c

Embora um pouco obscura, é principal vantagem é a rapidez e simplicidade. O loop while é apenas reiterou uma vez para cada conjunto de bits a 1 no n.

Answer 3

Você não pode fazer isso computacionalmente menos complexo. Será O (n) o número de bits, ou, como a resposta com o truque & mostrou, O (n) o número de bits colocados em 1; mas a menos que todos os números que você está usando são um caso especial, este último deve ser, em média n / 2, assim que ambos os O (n) números são os mesmos.

E o truque de pesquisa da tabela, é claro, está realmente fazendo nada para a complexidade computacional; é só pagando por tempo com o espaço, mas sem alterar a economia subjacente, que são que você deve examinar cada bit uma vez de alguma forma e não há maneira de contornar isso. Você não pode, logicamente, responder a uma pergunta sobre os bits do número sem inspecionar cada um deles.

Agora, eu suponho que eu estou sendo um pouco desleixado uma vez que muitos destes exemplos são, na verdade, O (n ^ 2) uma vez que em Python você tem que examinar o número inteiro de uma vez tempo, então com um Python inteiro longo de, digamos , 100 bytes, um + ou um & ou uma operação / vai olhar para cada byte de pelo menos uma vez, e que irá ocorrer repetidas vezes até que o número é reduzida a zero (em regimes descritos acima), de modo que estes, mais uma vez, são realmente O (n ^ 2) operações. Não estou certo de Python vai permitir um verdadeiro O (n) solução aqui.

De qualquer maneira: se você estava realmente perguntando sobre computacional complexidade, o que significa especificamente análise big-O, que é a sua resposta. : -)

Answer 4

Se você quiser fazê-lo em uma única linha, você poderia usar:

sum( [x&(1<<i)>0 for i in range(32)] )

Answer 5

Se você está realmente preocupado com a velocidade, o código-lo em C (ver esta questão por quanto), e interface com a implementação C usando algo como ctypes .

Answer 6

Aqui:

def bitCount (int_no):

c = 0
while(int_no):
    int_no &= (int_no - 1)
    c += 1
return c

Esta poderia ser uma forma antiga e eficiente de fazer isso ... originalmente implementated em C (Algo tem um nome não me lembro). Ele funciona muito bem para mim espero que ele faz para qualquer outra pessoa

Answer 7

p = lambda n: n e 1 + P (N & (n-1))

A usos curto-circuito e a recursividade, quando n é maior do que 0, comuta para calcular 1 + P (N & (n-1)) em que p (n & (n-1)) é chamado e assim por diante, quando n é 0 retorna 0. Complexidade ser o (n), uma vez que corre o número de vezes que o número de uns existir no binário.

Exemplo: p (9) = 1 + p (8) = 1 + 1 + P (0) = 1 + 1 + 0 = 2