Cuente los bits establecidos totales en todos los números del 1 al n | conjunto 2

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: 
 

Darse cuenta de, 
 

1. Se establecen todos los bits alternativos en A.
2. Cada 2 bits alternos en B se establecen.
3. Cada 4 bits alternos en C se establecen.
4. Cada 8 bits alternos en D se establecen.
5. …..
6. 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 ⁰ como A, 2 ¹ como B, 2 ² como C y 2 ³ 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 ⁰ = 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++ 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 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 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# 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

<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)