Как реализовать битовый набор в C?

Question

Я использовал класс Bitset на Java, и я хотел бы сделать что-то подобное в C. Предполагаю, что мне придется делать это вручную, как и большинство вещей в C. Что было бы эффективным способом реализации?

byte bitset[] 

возможно

bool bitset[] 

?

Answer 1

CCAN имеет реализацию BITSET вы можете использовать: http://ccan.ozlabs.org/info/jbitset.html

Но если вы в конечном итоге реализации его самостоятельно (например, если вам не нравятся зависимости от этого пакета), вы должны использовать массив Интса и использовать родной размер компьютерной архитектуры:

#define WORD_BITS (8 * sizeof(unsigned int)) 

unsigned int * bitarray = (int *)calloc(size/8 + 1, sizeof(unsigned int)); 

static inline void setIndex(unsigned int * bitarray, size_t idx) { 
    bitarray[idx/WORD_BITS] |= (1 << (idx % WORD_BITS)); 
} 

не использовать определенный размер (например, с uint64 или uint32), пусть компьютер использовать то, что он хочет использовать и адаптировать к этому с помощью SizeOf.

Answer 2

Ну, байт битрейт [] кажется мало вводить в заблуждение, нет?

Использование битовых полей в структуры, а затем вы можете сохранить набор этих типов (или использовать их иначе, как вы считаете нужным)

struct packed_struct { 
    unsigned int b1:1; 
    unsigned int b2:1; 
    unsigned int b3:1; 
    unsigned int b4:1; 
    /* etc. */ 
} packed; 

Answer 3

Сделать это массив неподписанных Int 64.

Answer 4

Как обычно, вам нужно сначала решить, какие операции вам нужно выполнять на вашем битете. Возможно, какое-то подмножество того, что определяет Java? После этого вы можете решить, как лучше всего его реализовать. Вы можете конечно посмотреть источник для BitSet.java в OpenJDK для идей.

Answer 5

Никто не говорил, что C FAQ рекомендует, что куча хороших-старослужащих макросов:

#include <limits.h>  /* for CHAR_BIT */ 

#define BITMASK(b) (1 << ((b) % CHAR_BIT)) 
#define BITSLOT(b) ((b)/CHAR_BIT) 
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b)) 
#define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b)) 
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b)) 
#define BITNSLOTS(nb) ((nb + CHAR_BIT - 1)/CHAR_BIT) 

(через http://c-faq.com/misc/bitsets.html)

Answer 6

Вы можете дать мой PackedArray код попробовать с bitsPerItem из 1.

Он реализует контейнер произвольного доступа, где элементы упакованы на уровне бит. Другими словами, он действует так, как будто вы можете манипулировать, например, uint9_t или uint17_t массив:

PackedArray principle: 
    . compact storage of <= 32 bits items 
    . items are tightly packed into a buffer of uint32_t integers 

PackedArray requirements: 
    . you must know in advance how many bits are needed to hold a single item 
    . you must know in advance how many items you want to store 
    . when packing, behavior is undefined if items have more than bitsPerItem bits 

PackedArray general in memory representation: 
    |-------------------------------------------------- - - - 
    |  b0  |  b1  |  b2  | 
    |-------------------------------------------------- - - - 
    | i0 | i1 | i2 | i3 | i4 | i5 | i6 | i7 | i8 | i9 | 
    |-------------------------------------------------- - - - 

    . items are tightly packed together 
    . several items end up inside the same buffer cell, e.g. i0, i1, i2 
    . some items span two buffer cells, e.g. i3, i6 

Answer 7

Я рекомендую мой BITSCAN C++ library (версия 1.0 только что был выпущен). BITSCAN специально ориентирован на быстрые операции с битами. Я использовал его для реализации комбинаторных задач NP-Hard с использованием простых неориентированных графов, таких как максимальная клика (см. Алгоритм BBMC, для ведущего точного решателя).

Сравнение между BITSCAN и стандартных растворов СТЛ BitSet и бустер dynamic_bitset доступна здесь: http://blog.biicode.com/bitscan-efficiency-at-glance/