Cuente los bits establecidos en un número entero usando la tabla de búsqueda

Escriba un programa eficiente para contar el número de 1 en representación binaria de un número entero.
Ejemplos 
 

Input : n = 6
Output : 2
Binary representation of 6 is 110 
and has 2 set bits

Input : n = 13
Output : 3
Binary representation of 11 is 1101 
and has 3 set bits

En el post anterior habíamos visto diferentes métodos que resolvían este problema en tiempo O(log n). En esta publicación, resolvemos en O (1) usando la tabla de búsqueda. Aquí asumimos que el tamaño de INT es de 32 bits. Es difícil contar los 32 bits de una sola vez usando la tabla de búsqueda («porque no es factible crear una tabla de búsqueda de tamaño 2 ³² -1″). Entonces , dividimos 32 bits en 8 bits de fragmentos (Cómo buscar en la tabla de tamaño (2 ⁸ -1) índice: 0-255).
Tabla de 
búsqueda En la historia de búsqueda, almacenamos el recuento de set_bit de cada 
número que está en un rango (0-255) 
LookupTable[0] = 0 | binario 00000000 CountSetBits 0 
LookupTable[1] = 1 | binario 00000001 CountSetBits 1 
LookupTable[2] = 1 | binario 00000010 CountSetBits 1 
Tabla de búsqueda [3] = 2 | binario 00000011 CountSetBits 2 
LookupTable[4] = 1 | binario 00000100 CountSetBits 1 
y así sucesivamente hasta LookupTable[255].
Tomemos un ejemplo de cómo funciona la tabla de búsqueda.
 

Let's number be : 354 
in Binary : 0000000000000000000000101100010

Split it into 8 bits chunks  :
In Binary  :  00000000 | 00000000 | 00000001 | 01100010
In decimal :     0          0          1         98

Now Count Set_bits using LookupTable
LookupTable[0] = 0
LookupTable[1] = 1
LookupTable[98] = 3

so Total bits count : 4 

// c++ count to count number of set bits
// using lookup table in O(1) time
 
#include <iostream>
using namespace std;
 
// Generate a lookup table for 32 bit integers
#define B2(n) n, n + 1, n + 1, n + 2
#define B4(n) B2(n), B2(n + 1), B2(n + 1), B2(n + 2)
#define B6(n) B4(n), B4(n + 1), B4(n + 1), B4(n + 2)
 
// Lookup table that store the reverse of each table
unsigned int lookuptable[256] = { B6(0), B6(1), B6(1), B6(2) };
 
// function countset Bits Using lookup table
// ans return set bits count
unsigned int countSetBits(int N)
{
    // first chunk of 8 bits from right
    unsigned int count = lookuptable[N & 0xff] +
 
                         // second chunk from  right
                         lookuptable[(N >> 8) & 0xff] +
                          
                         // third and fourth chunks
                         lookuptable[(N >> 16) & 0xff] +
                         lookuptable[(N >> 24) & 0xff];
    return count;
}
 
int main()
{
    unsigned int N = 354;
    cout << countSetBits(N) << endl;
 
    return 0;
}

// Java count to count number of set bits
// using lookup table in O(1) time
 
// Generate a lookup table for 32 bit integers
import java.util.*;
 
class GFG {
  static ArrayList<Integer> lookuptable
    = new ArrayList<Integer>();
 
  static void B2(int n)
  {
    lookuptable.add(n);
    lookuptable.add(n + 1);
    lookuptable.add(n + 1);
    lookuptable.add(n + 2);
  }
 
  static void B4(int n)
  {
    B2(n);
    B2(n + 1);
    B2(n + 1);
    B2(n + 2);
  }
 
  static void B6(int n)
  {
    B4(n);
    B4(n + 1);
    B4(n + 1);
    B4(n + 2);
  }
 
  // function countset Bits Using lookup table
  // ans return set bits count
  static int countSetBits(int N)
  {
    // adding the bits in chunks of 8 bits
    int count = lookuptable.get(N & 0xff)
      + lookuptable.get((N >> 8) & 0xff)
      + lookuptable.get((N >> 16) & 0xff)
      + lookuptable.get((N >> 24) & 0xff);
    return count;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    // Lookup table that store the reverse of each table
    B6(0);
    B6(1);
    B6(1);
    B6(2);
 
    int N = 354;
 
    // Function Call
    System.out.println(countSetBits(N));
  }
}
 
// This code is contributed by phasing17

# Python3 count to count number of set bits
# using lookup table in O(1) time
 
# Generate a lookup table for 32 bit integers
 
lookuptable = []
 
 
def B2(n):
    lookuptable.extend([n, n + 1, n + 1, n + 2])
 
 
def B4(n):
    B2(n), B2(n + 1), B2(n + 1), B2(n + 2)
 
 
def B6(n):
    B4(n), B4(n + 1), B4(n + 1), B4(n + 2)
 
 
# Lookup table that store the reverse of each table
lookuptable.extend([B6(0), B6(1), B6(1), B6(2)])
 
# function countset Bits Using lookup table
# ans return set bits count
 
 
def countSetBits(N):
 
    # adding the bits in chunks of 8 bits
    count = lookuptable[N & 0xff] + lookuptable[(N >> 8) & 0xff] + lookuptable[(
        N >> 16) & 0xff] + lookuptable[(N >> 24) & 0xff]
    return count
 
 
# Driver Code
N = 354
 
# Function Call
print(countSetBits(N))
 
 
# This code is contributed by phasing17

// JavaScript count to count number of set bits
// using lookup table in O(1) time
 
// Generate a lookup table for 32 bit integers
 
let lookuptable = [];
 
 
function B2(n)
{
    lookuptable.push(n);
    lookuptable.push(n + 1);
    lookuptable.push(n + 1);
    lookuptable.push(n + 2);
}
 
 
function B4(n)
{
    B2(n), B2(n + 1), B2(n + 1), B2(n + 2)
}
 
 
function B6(n)
{
    B4(n), B4(n + 1), B4(n + 1), B4(n + 2)
}
 
 
// Lookup table that store the reverse of each table
lookuptable.push(B6(0));
lookuptable.push(B6(1));
lookuptable.push(B6(1));
lookuptable.push(B6(2));
 
 
// function countset Bits Using lookup table
// ans return set bits count
function countSetBits(N)
{
    // adding the bits in chunks of 8 bits
    let count = lookuptable[N & 0xff] + lookuptable[(N >> 8) & 0xff] + lookuptable[(N >> 16) & 0xff] + lookuptable[(N >> 24) & 0xff];
    return count;
}
 
 
// Driver Code
let N = 354;
 
// Function Call
console.log(countSetBits(N));
 
 
// This code is contributed by phasing17

// C# count to count number of set bits
// using lookup table in O(1) time
 
// Generate a lookup table for 32 bit integers
 
using System;
using System.Collections.Generic;
 
class GFG {
    static List<int> lookuptable = new List<int>();
 
    static void B2(int n)
    {
        lookuptable.Add(n);
        lookuptable.Add(n + 1);
        lookuptable.Add(n + 1);
        lookuptable.Add(n + 2);
    }
 
    static void B4(int n)
    {
        B2(n);
        B2(n + 1);
        B2(n + 1);
        B2(n + 2);
    }
 
    static void B6(int n)
    {
        B4(n);
        B4(n + 1);
        B4(n + 1);
        B4(n + 2);
    }
 
    // function countset Bits Using lookup table
    // ans return set bits count
    static int countSetBits(int N)
    {
        // adding the bits in chunks of 8 bits
        int count = lookuptable[N & 0xff]
                    + lookuptable[(N >> 8) & 0xff]
                    + lookuptable[(N >> 16) & 0xff]
                    + lookuptable[(N >> 24) & 0xff];
        return count;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        // Lookup table that store the reverse of each table
        B6(0);
        B6(1);
        B6(1);
        B6(2);
 
        int N = 354;
 
        // Function Call
        Console.WriteLine(countSetBits(N));
    }
}
 
 
// This code is contributed by phasing17

Producción:  

4 

Complejidad de tiempo: O(1)

Complejidad espacial: O(1)