Dada una array de enteros de longitud N (un número arbitrariamente grande). ¿Cómo contar el número de bits establecidos en la array?
El enfoque simple sería crear un método eficiente para contar bits establecidos en una palabra (el tamaño más prominente, generalmente igual a la longitud de bits del procesador) y agregar bits de elementos individuales de la array.
Existen varios métodos para contar bits establecidos de un entero, vea esto por ejemplo. Estos métodos se ejecutan en el mejor de los casos O(logN) donde N es el número de bits. Tenga en cuenta que en un procesador N es fijo, el conteo se puede realizar en tiempo O(1) en una máquina de 32 bits, independientemente del conjunto total de bits. En general, los bits de la array se pueden calcular en tiempo O(n), donde ‘n’ es el tamaño de la array.
Sin embargo, una búsqueda en la tabla será un método más eficiente cuando el tamaño de la array sea grande. Tabla de almacenamiento de búsqueda que puede manejar 232 enteros no serán prácticos.
El siguiente código ilustra un programa simple para contar bits establecidos en una array de enteros de 64 K generada aleatoriamente. La idea es generar una búsqueda de los primeros 256 números (un byte) y dividir cada elemento de la array en el límite de bytes. Un metaprograma que usa el preprocesador C/C++ genera la tabla de búsqueda para contar los bits establecidos en un byte.
La derivación matemática detrás del metaprograma es evidente en la siguiente tabla (Agregue los índices de columna y fila para obtener el número, luego mire en la tabla para obtener bits establecidos en ese número. Por ejemplo, para obtener bits establecidos en 10, puede ser extraído de la fila denominada 8 y la columna denominada 2),
0, 1, 2, 3 0 - 0, 1, 1, 2 -------- GROUP_A(0) 4 - 1, 2, 2, 3 -------- GROUP_A(1) 8 - 1, 2, 2, 3 -------- GROUP_A(1) 12 - 2, 3, 3, 4 -------- GROUP_A(2) 16 - 1, 2, 2, 3 -------- GROUP_A(1) 20 - 2, 3, 3, 4 -------- GROUP_A(2) 24 - 2, 3, 3, 4 -------- GROUP_A(2) 28 - 3, 4, 4, 5 -------- GROUP_A(3) ... so on
De la tabla, surge un patrón en múltiplos de 4, tanto en la tabla como en el parámetro de grupo. La secuencia se puede generalizar como se muestra en el código.
Complejidad:
todas las operaciones toman O (1) excepto iterar sobre la array. La complejidad del tiempo es O(n) donde ‘n’ es el tamaño de la array. La complejidad del espacio depende del metaprograma que genera la búsqueda.
Código:
C++
#include <bits/stdc++.h>
#include <time.h>
using namespace std;
/* Size of array 64 K */
#define SIZE (1 << 16)
/* Meta program that generates set bit count
array of first 256 integers */
/* GROUP_A - When combined with META_LOOK_UP
generates count for 4x4 elements */
#define GROUP_A(x) x, x + 1, x + 1, x + 2
/* GROUP_B - When combined with META_LOOK_UP
generates count for 4x4x4 elements */
#define GROUP_B(x) GROUP_A(x), GROUP_A(x+1), GROUP_A(x+1), GROUP_A(x+2)
/* GROUP_C - When combined with META_LOOK_UP
generates count for 4x4x4x4 elements */
#define GROUP_C(x) GROUP_B(x), GROUP_B(x+1), GROUP_B(x+1), GROUP_B(x+2)
/* Provide appropriate letter to generate the table */
#define META_LOOK_UP(PARAMETER)\
GROUP_##PARAMETER(0),\
GROUP_##PARAMETER(1),\
GROUP_##PARAMETER(1),\
GROUP_##PARAMETER(2)\
int countSetBits(int array[], size_t array_size)
{
int count = 0;
/* META_LOOK_UP(C) - generates a table of 256 integers whose
sequence will be number of bits in i-th position
where 0 <= i < 256
*/
/* A static table will be much faster to access */
static unsigned char const look_up[] = { META_LOOK_UP(C) };
/* No shifting funds (for better readability) */
unsigned char *pData = NULL;
for(size_t index = 0; index < array_size; index++)
{
/* It is fine, bypass the type system */
pData = (unsigned char *)&array[index];
/* Count set bits in individual bytes */
count += look_up[pData[0]];
count += look_up[pData[1]];
count += look_up[pData[2]];
count += look_up[pData[3]];
}
return count;
}
/* Driver program, generates table of random 64 K numbers */
int main()
{
int index;
int random[SIZE];
/* Seed to the random-number generator */
srand((unsigned)time(0));
/* Generate random numbers. */
for( index = 0; index < SIZE; index++ )
{
random[index] = rand();
}
cout << "Total number of bits = "<< countSetBits(random, SIZE);
return 0;
}
// This is code is contributed by rathbhupendra
C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* Size of array 64 K */
#define SIZE (1 << 16)
/* Meta program that generates set bit count
array of first 256 integers */
/* GROUP_A - When combined with META_LOOK_UP
generates count for 4x4 elements */
#define GROUP_A(x) x, x + 1, x + 1, x + 2
/* GROUP_B - When combined with META_LOOK_UP
generates count for 4x4x4 elements */
#define GROUP_B(x) GROUP_A(x), GROUP_A(x+1), GROUP_A(x+1), GROUP_A(x+2)
/* GROUP_C - When combined with META_LOOK_UP
generates count for 4x4x4x4 elements */
#define GROUP_C(x) GROUP_B(x), GROUP_B(x+1), GROUP_B(x+1), GROUP_B(x+2)
/* Provide appropriate letter to generate the table */
#define META_LOOK_UP(PARAMETER) \
GROUP_##PARAMETER(0), \
GROUP_##PARAMETER(1), \
GROUP_##PARAMETER(1), \
GROUP_##PARAMETER(2) \
int countSetBits(int array[], size_t array_size)
{
int count = 0;
/* META_LOOK_UP(C) - generates a table of 256 integers whose
sequence will be number of bits in i-th position
where 0 <= i < 256
*/
/* A static table will be much faster to access */
static unsigned char const look_up[] = { META_LOOK_UP(C) };
/* No shifting funds (for better readability) */
unsigned char *pData = NULL;
for(size_t index = 0; index < array_size; index++)
{
/* It is fine, bypass the type system */
pData = (unsigned char *)&array[index];
/* Count set bits in individual bytes */
count += look_up[pData[0]];
count += look_up[pData[1]];
count += look_up[pData[2]];
count += look_up[pData[3]];
}
return count;
}
/* Driver program, generates table of random 64 K numbers */
int main()
{
int index;
int random[SIZE];
/* Seed to the random-number generator */
srand((unsigned)time(0));
/* Generate random numbers. */
for( index = 0; index < SIZE; index++ )
{
random[index] = rand();
}
printf("Total number of bits = %d\n", countSetBits(random, SIZE));
return 0;
}
Complejidad de tiempo: O(n)
Espacio auxiliar: O (tamaño)
Aportado por Venki . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA