Получить список бит, установленный в BitMap

Question

В C Есть ли оптимизированный способ получения списка битпотоков, установленных без разбора по каждому биту.

Рассмотрим следующий пример

int bitmap[4]; 

Итак, есть 4 * 32 бит Positions..Values ​​являются следующие

bitmap = { 0x1, 0x0, 0x0, 0x0010001 } 

Я хочу получить позиции каждого бита, установленного вместо разбора от 0 до 4 * 32 позиции.

Answer 1

Прежде всего, один не может реально использовать int для растрового изображения в C, поскольку сдвига немного влево, чтобы знаковый бит имеет неопределенное поведение, C не гарантирует, что представление двоичного дополнение, или что есть 32 бита в int; что, как говорится, самый простой способ избежать этих ловушек - использовать вместо этого uint32_t от <stdint.h>. Таким образом,

#include <stdint.h> 
uint32_t bitmap[4]; 

Так что считайте, что вы цифры этих бит 0 ... 127 из индексов 0 ... 3; и внутри индексов 0 ... 31; таким образом, вы можете получить индекс в массиве и разрядное число в пределах этого значения с помощью следующей формулы:

int bit_number = // a value from 0 ... 127 
int index = value >> 32; // shift right by number of bits in each index 
int bit_in_value = value & 31; // take modulo 32 to get the bit in value 

Теперь вы можете индексировать целое число от:

bitmap[index]; 

и битовую маску для желаемое значение

uint32_t mask = (uint32_t)1 << bit_in_value; 

так что вы можете проверить, если бит установлен, делая

bit_is_set = !!(bitmap[index] & mask); 

Теперь, чтобы ускорить работу, вы можете пропустить любой index, для которого bitmap[index] равен 0, потому что он не содержит никаких битов; аналогично, в каждом индексе вы можете ускорить процесс путем смещения бит в uint32_t из растрового изображения справа на 1 и маскировки с 1; и разорвать цикл, когда uint32_t становится 0:

for (int index = 0; index <= 3; index ++) { 
    uint32_t entry = bitmap[index]; 
    if (! entry) { 
     continue; 
    } 

    int bit_number = 32 * index; 
    while (entry) { 
     if (entry & 1) { 
      printf("bit number %d is set\n", bit_number); 
     } 
     entry >>= 1; 
     bit_number ++; 
    } 
} 

Кроме этого существует не так много, чтобы ускорить, кроме таблиц поиска, или с помощью встроенных функций компилятора, такие как this to set which is the lowest bit set, но вы все равно придется использовать некоторые все равно ,

Answer 2

Оптимальное решение, которое выполняется в O (k), где k = общее количество заданных битов во всем списке, может быть достигнуто с помощью таблицы поиска. Например, вы можете использовать таблицу из 256 записей для описания позиций бит каждого бита в этом байте. Индекс будет фактическим значением байта.

Для каждой записи вы можете использовать следующую структуру.

struct 
{ 
    int numberOfSetBits; 
    char* list; // use malloc and alloocate the list according to numberOfSetBits 
} 

Вы можете итерацию по элементу списка каждой структуры и числа итераций = число заданных битов для этого байта. Для 32-битного целого вам потребуется выполнить итерацию по 4 из этих структур, по одному на каждый байт. Чтобы определить, какую запись вам нужно проверить, вы используете Bitmap и сдвигаете 8 бит.Обратите внимание, что позиции битов относятся к этому байту, поэтому вам может потребоваться добавить смещение или 24, 16 или 8 в зависимости от байта, который вы выполняете (при условии 32-битного целого числа).

Примечание: если дополнительное использование памяти для вас не является проблемой, вы можете построить таблицу с 16 бит в 64 Кбайт, и вы уменьшите количество своих структур на половину.