Contar el número de 1 en representación binaria

Manera eficiente de contar el número de 1s en la representación binaria de un número en O (1) si tienes suficiente memoria para jugar. Esta es una pregunta de la entrevista que encontré en un foro en línea, pero no tenía respuesta. ¿Puede alguien sugerir algo, no puedo pensar en una forma de hacerlo en O (1) vez?

Ese es el problema de peso de Hamming , también conocido como conteo de población. El enlace menciona implementaciones eficientes. Citando:

Con memoria ilimitada, podríamos simplemente crear una tabla de búsqueda grande del peso de Hamming de cada entero de 64 bits

Tengo una solución que cuenta los bits en el tiempo O(Number of 1's) :

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

En el peor de los casos (cuando el número es 2 ^ n – 1, todos 1 en binario) comprobará cada bit.

Editar: Acabo de encontrar un muy buen algoritmo de memoria constante constante para bitcount. Aquí está, escrito en C:

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

Puede encontrar pruebas de su corrección aquí .

Tenga en cuenta el hecho de que: n & (n-1) siempre elimina el menos significativo 1.

Por lo tanto, podemos escribir el código para calcular el número de 1 de la siguiente manera:

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

La complejidad del progtwig sería: número de 1 en n (que es constantemente <32).

Vi la siguiente solución desde otro sitio web:

 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 ; } } 

¿Eso es?

Esa será la respuesta más corta en mi SO life: tabla de búsqueda.

Aparentemente, necesito explicar un poco: “si tienes suficiente memoria para jugar” significa, tenemos toda la memoria que necesitamos (sin importar la posibilidad técnica). Ahora, no necesita almacenar la tabla de búsqueda por más de un byte o dos. Aunque técnicamente será Ω (log (n)) en lugar de O (1), solo leer un número que necesita es Ω (log (n)), entonces si eso es un problema, entonces la respuesta es, imposible -que es incluso más corto.

¿Cuál de las dos respuestas esperan de usted en una entrevista? Nadie lo sabe.

Hay otro truco más: mientras que los ingenieros pueden tomar un número y hablar de Ω (log (n)), donde n es el número, los científicos informáticos dirán que en realidad debemos medir el tiempo de funcionamiento en función de la longitud de una entrada , entonces, lo que los ingenieros llaman Ω (log (n)) es en realidad Ω (k), donde k es el número de bytes. Aún así, como dije antes, solo leer un número es Ω (k), así que no hay forma de que podamos hacerlo mejor que eso.

A continuación funcionará también.

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

La función toma un int y devuelve el número de Uno en representación binaria

 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; } 

La siguiente es una solución C que utiliza 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; } 

La siguiente es una solución de Java que usa potencias 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; } 

A continuación hay dos ejemplos simples (en C ++) entre los cuales puedes hacer esto.

  1. Simplemente podemos contar los bits de set (1) usando __builtin_popcount ().

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

  2. Haz un bucle a través de todos los bits en un entero, comprueba si se ha establecido un bit y, si es así, incrementa la variable de conteo.

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

¡Espero que esto ayude!

Solo hay una manera en que puedo pensar para lograr esta tarea en O (1) … que es ‘hacer trampa’ y usar un dispositivo físico (con progtwigción lineal o incluso paralela, creo que el límite es O (log (k)) donde k representa el número de bytes del número).

Sin embargo, podría imaginar fácilmente un dispositivo físico que conecta cada bit y una línea de salida con un voltaje de 0/1. Entonces podría leer electrónicamente el voltaje total en una línea de ‘sum’ en O (1). Sería bastante fácil hacer que esta idea básica sea más elegante con algunos elementos básicos del circuito para producir la salida en la forma que desee (por ejemplo, una salida codificada binaria), pero la idea esencial es la misma y el circuito electrónico produciría la salida correcta estado en tiempo fijo.

Imagino que también existen posibles posibilidades de computación cuántica, pero si se nos permite hacer eso, creo que un simple circuito electrónico es la solución más fácil.

De hecho, he hecho esto usando un poco de prestidigitación: bastará con una sola tabla de búsqueda con 16 entradas y todo lo que tienes que hacer es dividir el representante binario en nibbles (tuplas de 4 bits). La complejidad es, de hecho, O (1) y escribí una plantilla C ++ que estaba especializada en el tamaño del número entero que quería (en # bits) … la convierte en una expresión constante en lugar de indeterminada.

Desde aquí puedes usar el hecho de que (i & -i) te devolverá el LS de un bit y simplemente repetirá el ciclo, eliminando el lsbit cada vez, hasta que el entero sea cero, pero ese es un viejo truco de paridad.

Vine aquí teniendo una gran creencia de que sé una hermosa solución para este problema. Código en C:

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

Pero después de investigar un poco sobre este tema (leer otras respuestas :)) encontré 5 algoritmos más eficientes. ¡Amar tan!

Incluso hay una instrucción de CPU diseñada específicamente para esta tarea: popcnt . (mencionado en esta respuesta )

Descripción y evaluación comparativa de muchos algoritmos que puedes encontrar aquí .

El siguiente método también puede contar el número de 1 en números negativos.

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

Sin embargo, un número como -1 se representa en binario como 11111111111111111111111111111111 y requerirá muchos cambios. Si no desea hacer tantos turnos para números negativos pequeños, otra forma podría ser la siguiente:

 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; } 

En python o en cualquier otra cadena convertir a bin, divídalo con ‘0’ para deshacerse de 0, luego combine y obtenga la longitud.

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

Al utilizar las operaciones de cadena de JS uno puede hacer lo siguiente;

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

o

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

Tuve que golf esto en Ruby y terminé con

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

Uso:

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

Obviamente no es eficiente, pero lo hace el truco 🙂

Implementación 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) 

Dos caminos::

 /* 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 

La mejor forma de javascript para hacerlo es

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

donde binaryValue es la cadena binaria, por ejemplo: 1100