Как набор может быть реализован в C / C ++ с использованием битового массива?

Question

Я читал во многих местах, что заданная структура данных может быть реализована в C ++ с использованием битового массива , но я не до конца понимаю это и пока Я не смог найти пример кода. У кого-нибудь есть пример или подробное объяснение?

Answer 1

Использование битового поля для реализации набора работает только в том случае, если в наборе есть только несколько возможных элементов, потому что вам нужен бит для каждого из них. Например, для набора битов всех 32-битных целых чисел потребуется 2 ^ 32 бит или около 500 мегабайт.

Хорошая новость заключается в том, что если существует достаточно мало возможных элементов, что пространство не является проблемой, оно действительно очень быстрое.

По сути, вы определяете битовый массив так, что каждый бит соответствует одному возможному элементу. Каждый бит, соответствующий элементу в наборе, равен 1; остальные 0.

Немного опубликует пример кода C (без каламбура). Я думаю, что C ++ может предложить прямую поддержку библиотек для наборов битов, но, к сожалению, я не говорю на этом.

РЕДАКТИРОВАТЬ: следующий пример кода, который я только что написал, предназначен для набора битов, который может содержать числа от 0 до 31. Разрешение поддержки произвольного числа элементов будет значительно более сложным, хотя, безусловно, полезным.

#include <stdint.h>
#include <stdio.h>

const BS_SIZE = 32;
typedef uint32_t bitset32;

/* Takes a pointer to a bit set and an int from 0 to 31,
 * and adds the int to the bit set.
 */
void add_element(bitset32 *bs, int elt)
{
    *bs |= (1 << elt);
}

/* Takes a pointer to a bit set and an int from 0 to 31,
 * and removes the int from the bit set.
 */
void remove_element(bitset32 *bs, int elt)
{
    *bs &= ~(1 << elt);
}

/* Takes a pointer to a bit set and an int from 0 to 31,
 * and returns 1 if the int is in the bit set, 0 otherwise.
 */
int has_element(bitset32 *bs, int elt)
{
    return (*bs >> elt) & 1;
}

/* Takes a pointer to a bit set and prints each element in it. */
void print_all_elements(bitset32 *bs)
{
    bitset32 bits = *bs;
    int i;
    for (i = 0; i < BS_SIZE; i++) {
        if (bits & 1) {
            printf("%d\n", i);
        }
        bits >>= 1;
    }
}

/* Some test code. Prints:
 * 0 in test
 * 0
 * 20
 * 31
 */
int main()
{
    bitset32 test = 0;
    add_element(&test, 0);
    add_element(&test, 13);
    add_element(&test, 13);
    add_element(&test, 20);
    add_element(&test, 28);
    remove_element(&test, 13);
    remove_element(&test, 20);
    remove_element(&test, 28);
    if (has_element(&test, 0)) {
        printf("0 in test\n");
    }
    if (has_element(&test, 20)) {
        printf("20 in test\n");
    }
    add_element(&test, 20);
    add_element(&test, 31);
    print_all_elements(&test);
    return 0;
}