Рубрики

Программа для подсчета количества установленных битов в (большом) массиве

Дан целочисленный массив длины N (произвольно большое число). Как посчитать количество установленных бит в массиве?

Простой подход заключается в создании эффективного метода для подсчета установленных битов в слове (наиболее заметный размер, обычно равный длине процессора в битах) и добавления битов из отдельных элементов массива.

Существуют различные методы подсчета установленных битов целого числа, см. Это, например. Эти методы работают в лучшем случае O (logN), где N — количество битов. Обратите внимание, что на процессоре N зафиксировано, подсчет может быть выполнен за O (1) время на 32-битной машине независимо от общего количества установленных бит. В целом, биты в массиве могут быть вычислены за время O (n), где 'n' — размер массива.

Тем не менее, поиск таблицы будет более эффективным методом при большом размере массива. Хранение таблицы поиска, которая может обрабатывать 2 32 целых числа, будет непрактичным.

Следующий код иллюстрирует простую программу для подсчета установленных битов в случайно сгенерированном массиве 64 K целых чисел. Идея состоит в том, чтобы сгенерировать поиск первых 256 чисел (один байт) и разбить каждый элемент массива на границе байта. Мета-программа, использующая препроцессор C / C ++, генерирует таблицу поиска для подсчета установленных битов в байте.

Математическое происхождение метапрограммы очевидно из следующей таблицы (добавьте индексы столбцов и строк, чтобы получить число, затем посмотрите в таблицу, чтобы получить установленные биты в этом числе. Например, чтобы получить установленные биты в 10, это может быть извлекается из строки с именем 8 и столбца с именем 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

Из таблицы есть шаблон, кратный 4, как в таблице, так и в параметре group. Последовательность может быть обобщена, как показано в коде.

Сложность:

Все операции занимают O (1), кроме итерации по массиву. Временная сложность составляет O (n), где 'n' — размер массива. Сложность пространства зависит от метапрограммы, которая генерирует поиск.

Код:

C ++

#include <bits/stdc++.h>
#include <time.h> 

using namespace std; 

  

  
/ * Размер массива 64 К * /
#define SIZE (1 << 16) 

  
/ * Мета-программа, которая генерирует установленное количество бит
массив первых 256 целых чисел * /

  
/ * GROUP_A - в сочетании с META_LOOK_UP
генерирует количество для элементов 4x4 * /

  
#define GROUP_A(x) x, x + 1, x + 1, x + 2 

  
/ * GROUP_B - в сочетании с META_LOOK_UP
генерирует количество для элементов 4x4x4 * /

  
#define GROUP_B(x) GROUP_A(x), GROUP_A(x+1), GROUP_A(x+1), GROUP_A(x+2) 

  
/ * GROUP_C - в сочетании с META_LOOK_UP
генерирует количество для элементов 4x4x4x4 * /

  
#define GROUP_C(x) GROUP_B(x), GROUP_B(x+1), GROUP_B(x+1), GROUP_B(x+2) 

  
/ * Предоставить соответствующее письмо для генерации таблицы * /

  
#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) - генерирует таблицу из 256 целых чисел, чьи

    последовательность будет числом бит в i-й позиции

    где 0 <= i <256

* /

  

    / * Доступ к статической таблице будет намного быстрее * /

    static unsigned char const look_up[] = { META_LOOK_UP(C) }; 

  

    / * Нет сдвига основы (для лучшей читаемости) * /

    unsigned char *pData = NULL; 

  

for(size_t index = 0; index < array_size; index++) 

    / * Хорошо, обходи систему типов * /

    pData = (unsigned char *)&array[index]; 

  

    / * Количество установленных бит в отдельных байтах * /

    count += look_up[pData[0]]; 

    count += look_up[pData[1]]; 

    count += look_up[pData[2]]; 

    count += look_up[pData[3]]; 

  

return count; 

  
/ * Драйверная программа, генерирует таблицу случайных чисел 64 К * /

int main() 

int index; 

int random[SIZE]; 

  
/ * Семя к генератору случайных чисел * /

srand((unsigned)time(0)); 

  
/ * Генерация случайных чисел. * /

for( index = 0; index < SIZE; index++ ) 

    random[index] = rand(); 

  

cout << "Total number of bits = "<< countSetBits(random, SIZE); 

return 0; 

  
// Это код, предоставленный rathbhupendra

С

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

  
/ * Размер массива 64 К * /
#define SIZE (1 << 16)

  
/ * Мета-программа, которая генерирует установленное количество бит

   массив первых 256 целых чисел * /

  
/ * GROUP_A - в сочетании с META_LOOK_UP

   генерирует количество для элементов 4x4 * /

  
#define GROUP_A(x) x, x + 1, x + 1, x + 2

  
/ * GROUP_B - в сочетании с META_LOOK_UP

   генерирует количество для элементов 4x4x4 * /

  
#define GROUP_B(x) GROUP_A(x), GROUP_A(x+1), GROUP_A(x+1), GROUP_A(x+2)

  
/ * GROUP_C - в сочетании с META_LOOK_UP

   генерирует количество для элементов 4x4x4x4 * /

  
#define GROUP_C(x) GROUP_B(x), GROUP_B(x+1), GROUP_B(x+1), GROUP_B(x+2)

  
/ * Предоставить соответствующее письмо для генерации таблицы * /

  
#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) - генерирует таблицу из 256 целых чисел, чьи

      последовательность будет числом бит в i-й позиции

      где 0 <= i <256

   * /

  

    / * Доступ к статической таблице будет намного быстрее * /

       static unsigned char const look_up[] = { META_LOOK_UP(C) };

  

    / * Нет сдвига основы (для лучшей читаемости) * /

    unsigned char *pData = NULL;

  

   for(size_t index = 0; index < array_size; index++)

   {

      / * Хорошо, обходи систему типов * /

      pData = (unsigned char *)&array[index];

  

      / * Количество установленных бит в отдельных байтах * /

      count += look_up[pData[0]];

      count += look_up[pData[1]];

      count += look_up[pData[2]];

      count += look_up[pData[3]];

   }

  

   return count;

}

  
/ * Драйверная программа, генерирует таблицу случайных чисел 64 К * /

int main()

{

   int index;

   int random[SIZE];

  

   / * Семя к генератору случайных чисел * /

   srand((unsigned)time(0));

  

   / * Генерация случайных чисел. * /

   for( index = 0; index < SIZE; index++ )

   {

      random[index] = rand();

   }

  

   printf("Total number of bits = %d\n", countSetBits(random, SIZE));

   return 0;

}

Внесено Венки . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Программа для подсчета количества установленных битов в (большом) массиве

0.00 (0%) 0 votes