Number of 1 Bits

+10

Você recebe um número inteiro não negativo n. Escreva n em binário e retorne quantos de seus dígitos são 1. Essa contagem também é chamada de número de bits definidos, contagem populacional ou peso de Hamming. Por exemplo, 6 é 110 em binário, então tem dois bits 1.

Função

hammingWeight(n: integer) → integer

ninteger: um número inteiro não negativo que cabe em um int de 32 bits com sinal
Retornainteger: o número de dígitos 1 na forma binária de n

Restrições

0 ≤ n ≤ 2³¹-1

Exemplos

Entrada: n = 11
Saída: 3
Explicação: 11 é 1011 em binário, que corresponde a 8 + 2 + 1. Três dos seus quatro dígitos binários são 1, então a resposta é 3.

Entrada: n = 128
Saída: 1
Explicação: 128 é 2^7, escrito como 10000000: um único 1 seguido de zeros, então a resposta é 1.

Para ir além

Se essa função fosse executada milhões de vezes, como você poderia contar os bits de um número de 32 bits com quatro consultas em uma tabela de 256 contagens pré-calculadas?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Percorra os dígitos binários de n sem construir uma string. Ler o último bit e deslocá-lo para fora leva uma etapa por dígito binário, até 31. Limpar o bit 1 menos significativo com n & (n-1) leva uma etapa por bit 1, exatamente o número da resposta.

Verifique o último bit e desloque para a direita

Intuição

n & 1 é o último dígito binário de n: 1 quando n é ímpar, 0 quando é par. Some-o à contagem. Então, n >> 1 descarta esse dígito e move o próximo para a última posição; para um número não negativo, isso equivale à divisão por 2, arredondada para baixo. Para 11, 1011, os últimos bits são 1, 1, 0 e 1 conforme n diminui até 0: três bits 1.

O loop para quando n é 0, então nunca percorre os zeros à esquerda: cerca de log2(n) etapas, 8 para 128 e no máximo 31. Ele armazena apenas n e a contagem.

Algoritmo

Inicie um contador em 0.
Enquanto n for maior que 0, adicione n & 1 ao contador.
Desloque n uma posição de bit para a direita.
Quando n chegar a 0, retorne o contador.

def hammingWeight(n):
    count = 0
    while n > 0:
        count += n & 1  # the last bit is 1 or 0
        n >>= 1         # drop the last bit
    return count

Limpe o bit definido de menor valor com n & (n-1)

Intuição

Subtrair 1 transforma o bit 1 mais baixo em 0 e cada 0 abaixo dele em 1, e deixa inalterados os bits acima. Portanto, n & (n-1) mantém os bits superiores e limpa o bit 1 mais baixo: 12 é 1100, 11 é 1011, e 1100 & 1011 é 1000.

Cada etapa remove exatamente um bit 1, então o número de etapas até n ser 0 é a resposta. 128 leva 1 etapa em vez de 8, embora 2^31-1 ainda leve 31. Lua 5.1 não tem operadores de bits, então sua versão encontra o bit 1 mais baixo dividindo por 2 repetidamente e subtrai esse valor; o loop ainda é executado uma vez para cada bit 1.

Algoritmo

Comece um contador em 0.
Enquanto n não for 0, substitua n por n & (n-1).
Adicione 1 ao contador após cada substituição.
Retorne o contador.

def hammingWeight(n):
    count = 0
    while n != 0:
        n &= n - 1  # turn off the lowest 1 bit
        count += 1
    return count

Armadilhas e casos extremos

Percorrer enquanto n > 1. O loop para antes do último bit 1 e retorna 0 para n = 1.
Dividir usando ponto flutuante. Em JavaScript, Lua e R, 11 / 2 é 5.5, e os restos seguintes são frações. Arredonde para baixo com Math.floor, math.floor ou %/%, ou use deslocamento de bits.
Escrever n & 1 no Lua 5.1. Ele não tem operadores de bits, então o código não compila; use n % 2 e math.floor(n / 2).

Perguntas frequentes3

Qual é a complexidade de tempo de Number of 1 Bits?

O loop de deslocamento é executado uma vez para cada dígito binário: O(log n), no máximo 31 etapas aqui. O loop n & (n-1) é executado uma vez para cada bit 1: O(k), em que k é a resposta. Ambos usam espaço extra O(1).

Existe uma função integrada que conta os bits definidos?

A maioria das linguagens tem uma, muitas vezes respaldada por uma única instrução do processador: Integer.bitCount em Java, __builtin_popcount no GCC, bits.OnesCount em Go, count_ones em Rust e int.bit_count no Python 3.10 e versões posteriores. Em uma entrevista, escreva o laço e mencione a função integrada.

Qual é a diferença entre peso de Hamming e distância de Hamming?

O peso de Hamming de um número é a quantidade de dígitos binários iguais a 1 que ele possui, e é isso que este problema retorna. A distância de Hamming entre dois números é a quantidade de posições de bits em que eles diferem: conte os bits 1 de a ^ b, pois o XOR define exatamente as posições em que eles diferem.

def hammingWeight(n):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

n = 11

Saída Esperada