Как реализовать битсет в C?

Question

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

byte bitset[]

возможно

bool bitset[]

?

Answer 1

CCAN имеет реализацию набора битов, которую вы можете использовать: 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

Никто не упомянул, что рекомендует 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 3

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

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

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

Answer 4

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

Сравнение между BITSCAN и стандартомРешения STL bitset и BOOST dynamic_bitset доступны здесь: http://blog.biicode.com/bitscan-efficiency-at-glance/

Answer 5

Вы можете попробовать мой код 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 6

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

Answer 7

Сделать это массивом unsigned int 64.