Número de contagem de 1s na representação binária

Maneira eficiente de contar o número de 1s na representação binária de um número em O (1) se você tiver memory suficiente para brincar. Esta é uma pergunta da entrevista que encontrei em um fórum online, mas não tinha resposta. Alguém pode sugerir algo, eu não posso pensar em uma maneira de fazê-lo em O (1) tempo?

Esse é o problema do peso de Hamming , também conhecido como contagem de população. O link menciona implementações eficientes. Citando:

Com memory ilimitada, poderíamos simplesmente criar uma grande tabela de consulta do peso Hamming de cada inteiro de 64 bits

Eu tenho uma solução que conta os bits no tempo O(Number of 1's) :

 bitcount(n): count = 0 while n > 0: count = count + 1 n = n & (n-1) return count 

No pior dos casos (quando o número é 2 ^ n-1, todos os 1’s em binário), ele verifica cada bit.

Edit: Acabei de encontrar um algoritmo de memory constante, tempo constante muito bom para bitcount. Aqui está, escrito em C:

 int BitCount(unsigned int u) { unsigned int uCount; uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111); return ((uCount + (uCount >> 3)) & 030707070707) % 63; } 

Você pode encontrar prova de sua correção aqui .

Observe o fato de que: n & (n-1) sempre elimina o menos significativo 1.

Assim, podemos escrever o código para calcular o número de 1s da seguinte forma:

 count=0; while(n!=0){ n = n&(n-1); count++; } cout<<"Number of 1's in n is: "< 

A complexidade do programa seria: número de 1s em n (que é constantemente <32).

Eu vi a seguinte solução de outro site:

 int count_one(int x){ x = (x & (0x55555555)) + ((x >> 1) & (0x55555555)); x = (x & (0x33333333)) + ((x >> 2) & (0x33333333)); x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f)); x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff)); x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff)); return x; } 
 public static void main(String[] args) { int a = 3; int orig = a; int count = 0; while(a>0) { a = a >> 1 << 1; if(orig-a==1) count++; orig = a >> 1; a = orig; } System.out.println("Number of 1s are: "+count); } 
  countBits(x){ y=0; while(x){ y += x & 1 ; x = x >> 1 ; } } 

é isso aí?

Essa será a resposta mais curta na minha vida SO: tabela de pesquisa.

Aparentemente, eu preciso explicar um pouco: “se você tem memory suficiente para brincar” significa que temos toda a memory que precisamos (esqueça a possibilidade técnica). Agora, você não precisa armazenar a tabela de consulta por mais de um byte ou dois. Embora tecnicamente seja Ω (log (n)) ao invés de O (1), apenas ler um número que você precisa é Ω (log (n)), então se isso é um problema, então a resposta é impossível – o que é ainda mais curto.

Qual das duas respostas eles esperam de você em uma entrevista, ninguém sabe.

Há ainda outro truque: enquanto os engenheiros podem pegar um número e falar sobre Ω (log (n)), onde n é o número, os cientistas da computação dirão que, na verdade, mediremos o tempo de execução como uma function de uma input Então, o que os engenheiros chamam de Ω (log (n)) é na verdade Ω (k), onde k é o número de bytes. Ainda assim, como eu disse antes, apenas ler um número é Ω (k), então não há como fazer melhor do que isso.

Abaixo vai funcionar também.

 nofone(int x) { a=0; while(x!=0) { x>>=1; if(x & 1) a++; } return a; } 

A function recebe um int e retorna o número de Ones na representação binária

 public static int findOnes(int number) { if(number < 2) { if(number == 1) { count ++; } else { return 0; } } value = number % 2; if(number != 1 && value == 1) count ++; number /= 2; findOnes(number); return count; } 

A seguir, uma solução C usando operadores de bits:

 int numberOfOneBitsInInteger(int input) { int numOneBits = 0; int currNum = input; while (currNum != 0) { if ((currNum & 1) == 1) { numOneBits++; } currNum = currNum >> 1; } return numOneBits; } 

A seguir, uma solução Java usando potências de 2:

 public static int numOnesInBinary(int n) { if (n < 0) return -1; int j = 0; while ( n > Math.pow(2, j)) j++; int result = 0; for (int i=j; i >=0; i--){ if (n >= Math.pow(2, i)) { n = (int) (n - Math.pow(2,i)); result++; } } return result; } 

Abaixo estão dois exemplos simples (em C ++) entre muitos pelos quais você pode fazer isso.

  1. Podemos simplesmente contar set bits (1’s) usando __builtin_popcount ().

    int numOfOnes(int x) { return __builtin_popcount(x); }

  2. Faça um loop em todos os bits em um inteiro, verifique se um bit está definido e, em seguida, se incrementa a variável count.

    int hammingDistance(int x) { int count = 0 for(int i = 0; i < 32; i++) if(x & (1 << i)) count++; return count; }

Espero que isto ajude!

Há apenas uma maneira em que posso pensar para realizar essa tarefa em O (1) … ou seja, “trapacear” e usar um dispositivo físico (com programação linear ou paralela, acho que o limite é O (log (k)) onde k representa o número de bytes do número).

No entanto, você pode facilmente imaginar um dispositivo físico que conecta cada bit a uma linha de saída com uma tensão 0/1. Então, você poderia ler eletronicamente a tensão total em uma linha de ‘sum’ em O (1). Seria muito fácil tornar essa idéia básica mais elegante com alguns elementos básicos do circuito para produzir a saída na forma que você quiser (por exemplo, uma saída codificada binária), mas a ideia essencial é a mesma e o circuito eletrônico produziria a saída correta estado em tempo fixo.

Eu imagino que também existem possibilidades possíveis de computação quântica, mas se pudermos fazer isso, eu pensaria que um simples circuito eletrônico é a solução mais fácil.

Na verdade, fiz isso usando um pouco de truque: uma única tabela de consulta com 16 inputs será suficiente e tudo o que você precisa fazer é dividir o representante binário em nibbles (tuplas de 4 bits). A complexidade é de fato O (1) e eu escrevi um modelo C ++ que era especializado no tamanho do inteiro que você queria (em # bits) … faz dele uma expressão constante ao invés de indeterminada.

fwiw você pode usar o fato de que (i & -i) irá retornar o LS de um bit e simplesmente loop, retirando o lsbit a cada vez, até que o inteiro seja zero – mas esse é um truque de paridade antigo.

Eu vim aqui tendo uma grande crença de que conheço uma bela solução para esse problema. Código em C:

  short numberOfOnes(unsigned int d) { short count = 0; for (; (d != 0); d &= (d - 1)) ++count; return count; } 

Mas depois que eu fiz uma pequena pesquisa sobre esse tópico (leia outras respostas :)) eu encontrei 5 algoritmos mais eficientes. AMOR!

Existe até uma instrução de CPU projetada especificamente para esta tarefa: popcnt . (mencionado nesta resposta )

Descrição e benchmarking de muitos algoritmos que você pode encontrar aqui .

O método abaixo também pode contar o número de 1s em números negativos.

 private static int countBits(int number) { int result = 0; while(number != 0) { result += number & 1; number = number >>> 1; } return result; } 

No entanto, um número como -1 é representado em binário como 11111111111111111111111111111111 e, portanto, vai exigir muita mudança. Se você não quiser fazer tantos turnos para pequenos números negativos, outra maneira poderia ser a seguinte:

 private static int countBits(int number) { boolean negFlag = false; if(number < 0) { negFlag = true; number = ~number; } int result = 0; while(number != 0) { result += number & 1; number = number >> 1; } return negFlag? (32-result): result; } 

Em python ou qualquer outra conversão para uma string bin dividir com ‘0’ para se livrar de 0 e depois combinar e obter o comprimento.

 len(''.join(str(bin(122011)).split('0')))-1 

Ao utilizar as operações de string do JS, pode-se fazer o seguinte;

 0b1111011.toString(2).split(/0|(?=.)/).length // returns 6 

ou

 0b1111011.toString(2).replace("0","").length // returns 6 

Eu tive que jogar golfe em ruby e terminei com

 l=->x{x.to_s(2).count ?1} 

Uso:

l[2**32-1] # returns 32

Obviamente não é eficiente, mas faz o truque 🙂

Implementação Ruby

 def find_consecutive_1(n) num = n.to_s(2) arr = num.split("") counter = 0 max = 0 arr.each do |x| if x.to_i==1 counter +=1 else max = counter if counter > max counter = 0 end max = counter if counter > max end max end puts find_consecutive_1(439) 

Dois caminhos::

 /* Method-1 */ int count1s(long num) { int tempCount = 0; while(num) { tempCount += (num & 1); //inc, based on right most bit checked num = num >> 1; //right shift bit by 1 } return tempCount; } /* Method-2 */ int count1s_(int num) { int tempCount = 0; std::string strNum = std::bitset< 16 >( num ).to_string(); // string conversion cout << "strNum=" << strNum << endl; for(int i=0; i 

Uso::

  int count = 0; count = count1s(0b00110011); cout << "count(0b00110011) = " << count << endl; //4 count = count1s(0b01110110); cout << "count(0b01110110) = " << count << endl; //5 count = count1s(0b00000000); cout << "count(0b00000000) = " << count << endl; //0 count = count1s(0b11111111); cout << "count(0b11111111) = " << count << endl; //8 count = count1s_(0b1100); cout << "count(0b1100) = " << count << endl; //2 count = count1s_(0b11111111); cout << "count(0b11111111) = " << count << endl; //8 count = count1s_(0b0); cout << "count(0b0) = " << count << endl; //0 count = count1s_(0b1); cout << "count(0b1) = " << count << endl; //1 

A melhor maneira de fazer isso em javascript é

 function getBinaryValue(num){ return num.toString(2); } function checkOnces(binaryValue){ return binaryValue.toString().replace(/0/g, "").length; } 

onde binaryValue é a cadeia binária, por exemplo: 1100