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

Dado un entero positivo N , la tarea es contar el número total de bits establecidos en representación binaria de todos los números del 1 al N .

Ejemplos: 

Entrada: N = 3 
Salida: 4 
setBits(1) + setBits(2) + setBits(3) = 1 + 1 + 2 = 4

Entrada: N = 6 
Salida: 9 
 

Enfoque: La solución a este problema se ha publicado en el Conjunto 1 y el Conjunto 2 de este artículo. Aquí, se discute un enfoque basado en   programación dinámica .

• Caso base: el número de bits establecidos en 0 es 0.
• Para cualquier número n: n y n>>1 tienen el mismo número de bits establecidos, excepto el bit más a la derecha.

Ejemplo: n = 11 ( 101 1), n ​​>> 1 = 5 ( 101 )… los mismos bits en 11 y 5 están marcados en negrita. Entonces, suponiendo que ya sabemos establecer el número de bits de 5, solo debemos tener cuidado con el bit más a la derecha de 11, que es 1. setBit (11) = setBit (5) + 1 = 2 + 1 = 3

El bit más a la derecha es 1 para impar y 0 para número par.

Relación de recurrencia: setBit(n) = setBit(n>>1) + (n & 1) y setBit(0) = 0

Podemos usar el enfoque de programación dinámica de abajo hacia arriba para resolver esto.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// set bits in all the integers
// from the range [1, n]
int countSetBits(int n)
{
 
    // To store the required count
    // of the set bits
    int cnt = 0;
 
    // To store the count of set
    // bits in every integer
    vector<int> setBits(n + 1);
 
    // 0 has no set bit
    setBits[0] = 0;
 
    for (int i = 1; i <= n; i++) {
 
        setBits[i] = setBits[i >> 1] + (i & 1);
    }
 
    // Sum all the set bits
    for (int i = 0; i <= n; i++) {
        cnt = cnt + setBits[i];
    }
 
    return cnt;
}
 
// Driver code
int main()
{
    int n = 6;
 
    cout << countSetBits(n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the count of
// set bits in all the integers
// from the range [1, n]
static int countSetBits(int n)
{
 
    // To store the required count
    // of the set bits
    int cnt = 0;
 
    // To store the count of set
    // bits in every integer
    int []setBits = new int[n + 1];
 
    // 0 has no set bit
    setBits[0] = 0;
 
    // For the rest of the elements
    for (int i = 1; i <= n; i++) {
 
        setBits[i] = setBits[i >> 1] + (i & 1);
    }
 
    // Sum all the set bits
    for (int i = 0; i <= n; i++)
    {
        cnt = cnt + setBits[i];
    }
    return cnt;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 6;
 
    System.out.println(countSetBits(n));
}
}
 
// This code is contributed by Princi Singh

# Python3 implementation of the approach
 
# Function to return the count of
# set bits in all the integers
# from the range [1, n]
def countSetBits(n):
 
    # To store the required count
    # of the set bits
    cnt = 0
 
    # To store the count of set
    # bits in every integer
    setBits = [0 for x in range(n + 1)]
 
    # 0 has no set bit
    setBits[0] = 0
 
    # For the rest of the elements
    for i in range(1, n + 1):
        setBits[i] = setBits[i // 2] + (i & 1)
 
    # Sum all the set bits
    for i in range(0, n + 1):
        cnt = cnt + setBits[i]
     
    return cnt
 
# Driver code
n = 6
print(countSetBits(n))
 
# This code is contributed by Sanjit Prasad

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to return the count of
    // set bits in all the integers
    // from the range [1, n]
    static int countSetBits(int n)
    {
     
        // To store the required count
        // of the set bits
        int cnt = 0;
     
        // To store the count of set
        // bits in every integer
        int []setBits = new int[n + 1];
     
        // 0 has no set bit
        setBits[0] = 0;
     
        // 1 has a single set bit
        setBits[1] = 1;
     
        // For the rest of the elements
        for (int i = 2; i <= n; i++)
        {
     
            // If current element i is even then
            // it has set bits equal to the count
            // of the set bits in i / 2
            if (i % 2 == 0)
            {
                setBits[i] = setBits[i / 2];
            }
     
            // Else it has set bits equal to one
            // more than the previous element
            else
            {
                setBits[i] = setBits[i - 1] + 1;
            }
        }
     
        // Sum all the set bits
        for (int i = 0; i <= n; i++)
        {
            cnt = cnt + setBits[i];
        }
        return cnt;
    }
     
    // Driver code
    static public void Main ()
    {
        int n = 6;
     
        Console.WriteLine(countSetBits(n));
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
// Javascript implementation of the approach
 
// Function to return the count of
// set bits in all the integers
// from the range [1, n]
function countSetBits(n)
{
     
    // To store the required count
    // of the set bits
    var cnt = 0;
 
    // To store the count of set
    // bits in every integer
    var setBits = Array.from(
        {length: n + 1}, (_, i) => 0);
 
    // 0 has no set bit
    setBits[0] = 0;
 
    // 1 has a single set bit
    setBits[1] = 1;
 
    // For the rest of the elements
    for(i = 2; i <= n; i++)
    {
         
        // If current element i is even then
        // it has set bits equal to the count
        // of the set bits in i / 2
        if (i % 2 == 0)
        {
            setBits[i] = setBits[i / 2];
        }
 
        // Else it has set bits equal to one
        // more than the previous element
        else
        {
            setBits[i] = setBits[i - 1] + 1;
        }
    }
 
    // Sum all the set bits
    for(i = 0; i <= n; i++)
    {
        cnt = cnt + setBits[i];
    }
    return cnt;
}
 
// Driver code
var n = 6;
 
document.write(countSetBits(n));
 
// This code is contributed by 29AjayKumar
 
</script>

9

Otra solución simple y fácil de entender:

Una solución simple, fácil de implementar y comprender sería no usar operaciones de bits. La solución es contar directamente los bits establecidos usando __builtin_popcount(). La solución se explica en el código usando comentarios.

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// set bits in all the integers
// from the range [1, n]
int countSetBits(int n)
{
 
    // To store the required count
    // of the set bits
    int cnt = 0;
 
    // Calculate set bits in each number using
    // __builtin_popcount() and  Sum all the set bits
    for (int i = 1; i <= n; i++) {
        cnt = cnt + __builtin_popcount(i);
    }
 
    return cnt;
}
 
// Driver code
int main()
{
    int n = 6;
 
    cout << countSetBits(n);
 
    return 0;
}
 
// This article is contributed by Abhishek

// Java implementation of the approach
import java.util.*;
 
class GFG{
 
// Function to return the count of
// set bits in all the integers
// from the range [1, n]
static int countSetBits(int n)
{
 
    // To store the required count
    // of the set bits
    int cnt = 0;
 
    // Calculate set bits in each number using
    // Integer.bitCount() and  Sum all the set bits
    for (int i = 1; i <= n; i++) {
        cnt = cnt + Integer.bitCount(i);
    }
 
    return cnt;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 6;
    System.out.print(countSetBits(n));
 
}
}
 
// This code is contributed by Rajput-Ji

# Python implementation of the approach
 
# Function to return the count of
# set bits in all the integers
# from the range [1, n]
def countSetBits(n):
 
    # To store the required count
    # of the set bits
    cnt = 0;
 
    # Calculate set bits in each number using
    # Integer.bitCount() and Sum all the set bits
    for i in range(1,n+1):
        cnt = cnt + (bin(i)[2:]).count('1');
     
    return cnt;
 
# Driver code
if __name__ == '__main__':
    n = 6;
    print(countSetBits(n));
 
# This code is contributed by Rajput-Ji

// C# implementation of the approach
using System;
using System.Linq;
 
public class GFG{
 
  // Function to return the count of
  // set bits in all the integers
  // from the range [1, n]
  static int countSetBits(int n)
  {
 
    // To store the required count
    // of the set bits
    int cnt = 0;
 
    // Calculate set bits in each number using
    // int.bitCount() and  Sum all the set bits
    for (int i = 1; i <= n; i++) {
      cnt = cnt + (Convert.ToString(i, 2).Count(c => c == '1'));
    }
 
    return cnt;
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    int n = 6;
    Console.Write(countSetBits(n));
 
  }
}
 
// This code is contributed by Rajput-Ji

<script>
// javascript implementation of the approach
 
function bitCount (n) {
  n = n - ((n >> 1) & 0x55555555)
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
  return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24
}
    // Function to return the count of
    // set bits in all the integers
    // from the range [1, n]
    function countSetBits(n) {
 
        // To store the required count
        // of the set bits
        var cnt = 0;
 
        // Calculate set bits in each number using
        // Integer.bitCount() and Sum all the set bits
        for (i = 1; i <= n; i++) {
            cnt = cnt + bitCount(i);
        }
 
        return cnt;
    }
 
    // Driver code
        var n = 6;
        document.write(countSetBits(n));
 
// This code is contributed by Rajput-Ji
</script>

9

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.