Dado un entero positivo N , la tarea es contar la suma del número de bits establecidos en la representación binaria de todos los números del 1 al N .
Ejemplos:
Entrada: N = 3
Salida: 4
Decimal Binario Establecer recuento de bits 1 01 1 2 10 1 3 11 2 1 + 1 + 2 = 4
Entrada: N = 16
Salida: 33
Enfoque: Aquí se han discutido algunos otros enfoques para resolver este problema . En este artículo, se ha discutido otro enfoque con complejidad temporal O(logN).
Comprueba el patrón de representación Binaria de los números del 1 al N en la siguiente tabla:
Decimal | mi | D | C | B | A |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 0 | 1 |
2 | 0 | 0 | 0 | 1 | 0 |
3 | 0 | 0 | 0 | 1 | 1 |
4 | 0 | 0 | 1 | 0 | 0 |
5 | 0 | 0 | 1 | 0 | 1 |
6 | 0 | 0 | 1 | 1 | 0 |
7 | 0 | 0 | 1 | 1 | 1 |
8 | 0 | 1 | 0 | 0 | 0 |
9 | 0 | 1 | 0 | 0 | 1 |
10 | 0 | 1 | 0 | 1 | 0 |
11 | 0 | 1 | 0 | 1 | 1 |
12 | 0 | 1 | 1 | 0 | 0 |
13 | 0 | 1 | 1 | 0 | 1 |
14 | 0 | 1 | 1 | 1 | 0 |
15 | 0 | 1 | 1 | 1 | 1 |
dieciséis | 1 | 0 | 0 | 0 | 0 |
Darse cuenta de,
- Se establecen todos los bits alternativos en A.
- Cada 2 bits alternos en B se establecen.
- Cada 4 bits alternos en C se establecen.
- Cada 8 bits alternos en D se establecen.
- …..
- Esto seguirá repitiéndose para cada potencia de 2.
Entonces, iteramos hasta la cantidad de bits en el número. Y no tenemos que iterar cada número en el rango de 1 a n.
Realizaremos las siguientes operaciones para obtener el resultado deseado.
- , En primer lugar, agregaremos 1 al número para compensar 0. Como el sistema de números binarios comienza desde 0, ahora n = n + 1.
- Llevaremos la cuenta del número de bits establecidos encontrados hasta ahora. Y lo inicializaremos con n/2.
- Mantendremos una variable que es una potencia de 2, para realizar un seguimiento de los bits que estamos calculando.
- Iteramos hasta que la potencia de 2 sea mayor que n.
- Podemos obtener el número de pares de 0 y 1 en el bit actual para todos los números dividiendo n por la potencia actual de 2.
- Ahora tenemos que sumar los bits en el conteo de bits establecido. Podemos hacer esto dividiendo el número de pares de 0 y 1 entre 2, lo que nos dará el número de pares de 1 solamente y después de eso, multiplicaremos eso con la potencia actual de 2 para obtener el conteo de unos en los grupos. .
- Ahora puede haber una posibilidad de que obtengamos un número como número de pares, que está en algún lugar en el medio del grupo, es decir, el número de 1 es menor que la potencia actual de 2 en ese grupo en particular. Entonces, encontraremos el módulo y lo agregaremos al conteo de bits establecidos, lo cual quedará claro con la ayuda de un ejemplo.
Ejemplo: Considere N = 14
De la tabla anterior, habrá 28 bits establecidos en total del 1 al 14.
Consideraremos 2 0 como A, 2 1 como B, 2 2 como C y 2 3 como D
En primer lugar agregaremos 1 al número N, así que ahora nuestro N = 14 + 1 = 15.
^ representa elevar a la potencia, no XOR.
p.ej. 2^3 significa 2 elevados a 3.
- Cálculo para A (2 0 = 1)
15/2 = 7
Número de bits establecidos en A = 7 ————> (i) - Cálculo para B (2^1 = 2)
15/2 = 7 => hay 7 grupos de 0 y 1
Ahora, para calcular el número de grupos de bits establecidos solamente, tenemos que dividirlo por 2.
Entonces, 7/2 = 3. Hay 3 grupos de bits establecidos.
Y estos grupos contendrán bits establecidos iguales a la potencia de 2 esta vez, que es 2. Por lo tanto, multiplicaremos el número de grupos de bits establecidos con una potencia de 2
=> 3*2 = 6 —>(2i)
Además
, puede haber algo adicional 1 en esto porque no se considera el cuarto grupo, ya que esta división solo nos dará un valor entero. Así que tenemos que agregar eso también. Nota: – Esto sucederá solo cuando el número de grupos de 0 y 1 sea impar.
15%2 = 1 —>(2ii)
2i + 2ii => 6 + 1 = 7 ————>(ii) - Cálculo para C (2^2 = 4)
15/4 = 3 => hay 3 grupos de 0 y 1
Número de grupos de bits establecidos = 3/2 = 1
Número de bits establecidos en esos grupos = 1*4 = 4 — > (3i)
Como 3 es impar, hay que sumar bits en el grupo que no se considera
Entonces, 15%4 = 3 —> (3ii)
3i + 3ii = 4 + 3 = 7 ————>(iii) - Cálculo para D (2^3 = 8)
15/8 = 1 => hay 1 grupo de 0 y 1. Ahora, en este caso, solo hay un grupo y también de solo 0.
Número de grupos de bits establecidos = 1/2 = 0
Número de bits establecidos en esos grupos = 0 * 8 = 0 —> (4i)
Como número de grupos son impar,
Entonces, 15%8 = 7 —> (4ii)
4i + 4ii = 0 + 7 = 7 ————>(iv)
En este punto, nuestra variable potencia de 2 se vuelve mayor que el número, que es 15 en nuestro caso. (potencia de 2 = 16 y 16 > 15). Así que el ciclo se termina aquí.
Salida final = i + ii + iii + iv = 7 + 7 + 7 + 7 = 28
El número de bits establecidos de 1 a 14 es 28.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <iostream> using namespace std; // Function to return the sum of the count // of set bits in the integers from 1 to n int countSetBits(int n) { // Ignore 0 as all the bits are unset n++; // To store the powers of 2 int powerOf2 = 2; // To store the result, it is initialized // with n/2 because the count of set // least significant bits in the integers // from 1 to n is n/2 int cnt = n / 2; // Loop for every bit required to represent n while (powerOf2 <= n) { // Total count of pairs of 0s and 1s int totalPairs = n / powerOf2; // totalPairs/2 gives the complete // count of the pairs of 1s // Multiplying it with the current power // of 2 will give the count of // 1s in the current bit cnt += (totalPairs / 2) * powerOf2; // If the count of pairs was odd then // add the remaining 1s which could // not be groupped together cnt += (totalPairs & 1) ? (n % powerOf2) : 0; // Next power of 2 powerOf2 <<= 1; } // Return the result return cnt; } // Driver code int main() { int n = 14; cout << countSetBits(n); return 0; }
Java
// Java implementation of the approach class GFG { // Function to return the sum of the count // of set bits in the integers from 1 to n static int countSetBits(int n) { // Ignore 0 as all the bits are unset n++; // To store the powers of 2 int powerOf2 = 2; // To store the result, it is initialized // with n/2 because the count of set // least significant bits in the integers // from 1 to n is n/2 int cnt = n / 2; // Loop for every bit required to represent n while (powerOf2 <= n) { // Total count of pairs of 0s and 1s int totalPairs = n / powerOf2; // totalPairs/2 gives the complete // count of the pairs of 1s // Multiplying it with the current power // of 2 will give the count of // 1s in the current bit cnt += (totalPairs / 2) * powerOf2; // If the count of pairs was odd then // add the remaining 1s which could // not be groupped together cnt += (totalPairs % 2 == 1) ? (n % powerOf2) : 0; // Next power of 2 powerOf2 <<= 1; } // Return the result return cnt; } // Driver code public static void main(String[] args) { int n = 14; System.out.println(countSetBits(n)); } } // This code is contributed by Princi Singh
Python3
# Python3 implementation of the approach # Function to return the sum of the count # of set bits in the integers from 1 to n def countSetBits(n) : # Ignore 0 as all the bits are unset n += 1; # To store the powers of 2 powerOf2 = 2; # To store the result, it is initialized # with n/2 because the count of set # least significant bits in the integers # from 1 to n is n/2 cnt = n // 2; # Loop for every bit required to represent n while (powerOf2 <= n) : # Total count of pairs of 0s and 1s totalPairs = n // powerOf2; # totalPairs/2 gives the complete # count of the pairs of 1s # Multiplying it with the current power # of 2 will give the count of # 1s in the current bit cnt += (totalPairs // 2) * powerOf2; # If the count of pairs was odd then # add the remaining 1s which could # not be groupped together if (totalPairs & 1) : cnt += (n % powerOf2) else : cnt += 0 # Next power of 2 powerOf2 <<= 1; # Return the result return cnt; # Driver code if __name__ == "__main__" : n = 14; print(countSetBits(n)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach using System; class GFG { // Function to return the sum of the count // of set bits in the integers from 1 to n static int countSetBits(int n) { // Ignore 0 as all the bits are unset n++; // To store the powers of 2 int powerOf2 = 2; // To store the result, it is initialized // with n/2 because the count of set // least significant bits in the integers // from 1 to n is n/2 int cnt = n / 2; // Loop for every bit required to represent n while (powerOf2 <= n) { // Total count of pairs of 0s and 1s int totalPairs = n / powerOf2; // totalPairs/2 gives the complete // count of the pairs of 1s // Multiplying it with the current power // of 2 will give the count of // 1s in the current bit cnt += (totalPairs / 2) * powerOf2; // If the count of pairs was odd then // add the remaining 1s which could // not be groupped together cnt += (totalPairs % 2 == 1) ? (n % powerOf2) : 0; // Next power of 2 powerOf2 <<= 1; } // Return the result return cnt; } // Driver code public static void Main(String[] args) { int n = 14; Console.WriteLine(countSetBits(n)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // javascript implementation of the approach// Function to return the sum of the count // of set bits in the integers from 1 to n function countSetBits(n) { // Ignore 0 as all the bits are unset n++; // To store the powers of 2 var powerOf2 = 2; // To store the result, it is initialized // with n/2 because the count of set // least significant bits in the integers // from 1 to n is n/2 var cnt = n / 2; // Loop for every bit required to represent n while (powerOf2 <= n) { // Total count of pairs of 0s and 1s var totalPairs = n / powerOf2; // totalPairs/2 gives the complete // count of the pairs of 1s // Multiplying it with the current power // of 2 will give the count of // 1s in the current bit cnt += (totalPairs / 2) * powerOf2; // If the count of pairs was odd then // add the remaining 1s which could // not be groupped together cnt += (totalPairs % 2 == 1) ? (n % powerOf2) : 0; // Next power of 2 powerOf2 <<= 1; } // Return the result return cnt; } // Driver code var n = 14; document.write(countSetBits(n)); // This code is contributed by 29AjayKumar </script>
28
Complejidad de tiempo: O (log n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Sumit Makkar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA