Эффективный бит бит C/С++

Ответ 1

boost::dynamic_bitset, если длина известна только во время выполнения.

std::bitset, если длина известна во время компиляции (хотя произвольно).

Ответ 2

Поскольку вы упоминаете C и С++, я предполагаю, что решение на основе С++, такое как boost::dynamic_bitset, может быть неприменимо, и вместо этого говорить о реализации на низком уровне C. Обратите внимание, что если что-то вроде boost::dynamic_bitset работает для вас или существует ранее существовавшая библиотека C, которую вы можете найти, то использование их может быть лучше, чем сворачивать ваши собственные.

Предупреждение. Ни один из следующих кодов не был протестирован или даже не скомпилирован, но он должен быть очень близок к тому, что вам нужно.

Для начала предположим, что у вас есть фиксированный размер набора бит N. Затем происходит следующее:

typedef uint32_t word_t;
enum { WORD_SIZE = sizeof(word_t) * 8 };

word_t data[N / 32 + 1];

inline int bindex(int b) { return b / WORD_SIZE; }
inline int boffset(int b) { return b % WORD_SIZE; }

void set_bit(int b) { 
    data[bindex(b)] |= 1 << (boffset(b)); 
}
void clear_bit(int b) { 
    data[bindex(b)] &= ~(1 << (boffset(b)));
}
int get_bit(int b) { 
    return data[bindex(b)] & (1 << (boffset(b));
}
void clear_all() { /* set all elements of data to zero */ }
void set_all() { /* set all elements of data to one */ }

Как написано, это немного грубо, поскольку он реализует только один глобальный битсет с фиксированным размером. Чтобы устранить эти проблемы, вы хотите начать с строки данных следующим образом:

struct bitset { word_t *words; int nwords; };

а затем записывать функции для создания и уничтожения этих битов.

struct bitset *bitset_alloc(int nbits) {
    struct bitset *bitset = malloc(sizeof(*bitset));
    bitset->nwords = (n / WORD_SIZE + 1);
    bitset->words = malloc(sizeof(*bitset->words) * bitset->nwords);
    bitset_clear(bitset);
    return bitset;
}

void bitset_free(struct bitset *bitset) {
    free(bitset->words);
    free(bitset);
}

Теперь, относительно просто изменить предыдущие функции, чтобы принять параметр struct bitset *. До сих пор нет способа изменить размер бита в течение его жизненного цикла, и нет никаких ограничений на проверку границ, но в этот момент их не будет сложно добавить.

Ответ 3

Я написал рабочую реализацию, основанную на ответе Dale Hagglund, чтобы предоставить бит-массив в C (лицензия BSD).

https://github.com/noporpoise/BitArray/

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

Ответ 4

Эта публикация довольно старая, но в моей библиотеке ALFLB есть эффективный набор бит-бит в C.

Для многих микроконтроллеров без кода операции аппаратного деления эта библиотека ЭФФЕКТИВНО, потому что она не использует деление: вместо этого используются маскировка и смещение бит. (Да, я знаю, что некоторые компиляторы преобразуют деление на 8 в сдвиг, но это зависит от компилятора от компилятора.)

Он был протестирован на массивах до 2 ^ 32-2 бит (около 4 миллиардов бит, хранящихся в 536 Мбайтах), хотя последние 2 бита должны быть доступны, если они не используются в for-loop в вашем приложении.

См. ниже выдержку из doco. Doco http://alfredo4570.net/src/alflb_doco/alflb.pdf, библиотека http://alfredo4570.net/src/alflb.zip

Наслаждайтесь,
Alf

//------------------------------------------------------------------
BM_DECLARE( arrayName, bitmax);
        Macro to instantiate an array to hold bitmax bits.
//------------------------------------------------------------------
UCHAR *BM_ALLOC( BM_SIZE_T bitmax); 
        mallocs an array (of unsigned char) to hold bitmax bits.
        Returns: NULL if memory could not be allocated.
//------------------------------------------------------------------
void BM_SET( UCHAR *bit_array, BM_SIZE_T bit_index);
        Sets a bit to 1.
//------------------------------------------------------------------
void BM_CLR( UCHAR *bit_array, BM_SIZE_T bit_index);
        Clears a bit to 0.
//------------------------------------------------------------------
int BM_TEST( UCHAR *bit_array, BM_SIZE_T bit_index); 
        Returns: TRUE (1) or FALSE (0) depending on a bit.
//------------------------------------------------------------------
int BM_ANY( UCHAR *bit_array, int value, BM_SIZE_T bitmax); 
        Returns: TRUE (1) if array contains the requested value (i.e. 0 or 1).
//------------------------------------------------------------------
UCHAR *BM_ALL( UCHAR *bit_array, int value, BM_SIZE_T bitmax);
        Sets or clears all elements of a bit array to your value. Typically used after a BM_ALLOC.  
        Returns: Copy of address of bit array
//------------------------------------------------------------------
void BM_ASSIGN( UCHAR *bit_array, int value, BM_SIZE_T bit_index);
        Sets or clears one element of your bit array to your value.
//------------------------------------------------------------------
BM_MAX_BYTES( int bit_max); 
        Utility macro to calculate the number of bytes to store bitmax bits.
        Returns: A number specifying the number of bytes required to hold bitmax bits.
//------------------------------------------------------------------

Ответ 5

Вы можете использовать std:: bitset

int main() {
  const bitset<12> mask(2730ul); 
  cout << "mask =      " << mask << endl;

  bitset<12> x;

  cout << "Enter a 12-bit bitset in binary: " << flush;
  if (cin >> x) {
    cout << "x =        " << x << endl;
    cout << "As ulong:  " << x.to_ulong() << endl;
    cout << "And with mask: " << (x & mask) << endl;
    cout << "Or with mask:  " << (x | mask) << endl;
  }
}

Ответ 6

Я знаю, что это старое сообщение, но я пришел сюда, чтобы найти простую реализацию битов C, и ни один из ответов не соответствовал тому, что я искал, поэтому я реализовал свою собственную на основе ответа Дейла Хаглунда. Вот он:)

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

typedef uint32_t word_t;
enum { BITS_PER_WORD = 32 };
struct bitv { word_t *words; int nwords; int nbits; };

struct bitv* bitv_alloc(int bits) {
    struct bitv *b = malloc(sizeof(struct bitv));

    if (b == NULL) {
        fprintf(stderr, "Failed to alloc bitv\n");
        exit(1);
    }

    b->nwords = (bits >> 5) + 1;
    b->nbits  = bits;
    b->words  = malloc(sizeof(*b->words) * b->nwords);

    if (b->words == NULL) {
        fprintf(stderr, "Failed to alloc bitv->words\n");
        exit(1);
    }

    memset(b->words, 0, sizeof(*b->words) * b->nwords);

    return b;
}

static inline void check_bounds(struct bitv *b, int bit) {
    if (b->nbits < bit) {
        fprintf(stderr, "Attempted to access a bit out of range\n");
        exit(1);
    }
}

void bitv_set(struct bitv *b, int bit) {
    check_bounds(b, bit);
    b->words[bit >> 5] |= 1 << (bit % BITS_PER_WORD);
}

void bitv_clear(struct bitv *b, int bit) {
    check_bounds(b, bit);
    b->words[bit >> 5] &= ~(1 << (bit % BITS_PER_WORD));
}

int bitv_test(struct bitv *b, int bit) {
    check_bounds(b, bit);
    return b->words[bit >> 5] & (1 << (bit % BITS_PER_WORD));
}

void bitv_free(struct bitv *b) {
    if (b != NULL) {
        if (b->words != NULL) free(b->words);
        free(b);
    }
}

void bitv_dump(struct bitv *b) {
    if (b == NULL) return;

    for(int i = 0; i < b->nwords; i++) {
        word_t w = b->words[i];

        for (int j = 0; j < BITS_PER_WORD; j++) {
            printf("%d", w & 1);
            w >>= 1;
        }

        printf(" ");
    }

    printf("\n");
}

void test(struct bitv *b, int bit) {
    if (bitv_test(b, bit)) printf("Bit %d is set!\n", bit);
    else                   printf("Bit %d is not set!\n", bit);
}

int main(int argc, char *argv[]) {
    struct bitv *b = bitv_alloc(32);

    bitv_set(b, 1);
    bitv_set(b, 3);
    bitv_set(b, 5);
    bitv_set(b, 7);
    bitv_set(b, 9);
    bitv_set(b, 32);
    bitv_dump(b);
    bitv_free(b);

    return 0;
}

Ответ 7

Я использую этот:

//#include <bitset>
#include <iostream>
//source http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c
#define BIT_SET(a,b) ((a) |= (1<<(b)))
#define BIT_CLEAR(a,b) ((a) &= ~(1<<(b)))
#define BIT_FLIP(a,b) ((a) ^= (1<<(b)))
#define BIT_CHECK(a,b) ((a) & (1<<(b)))

/* x=target variable, y=mask */
#define BITMASK_SET(x,y) ((x) |= (y))
#define BITMASK_CLEAR(x,y) ((x) &= (~(y)))
#define BITMASK_FLIP(x,y) ((x) ^= (y))
#define BITMASK_CHECK(x,y) ((x) & (y))

Ответ 8

Недавно я выпустил BITSCAN, библиотеку битовых строк С++, которая специально ориентирована на операции быстрого сверления бит. BITSCAN доступен здесь. Он находится в альфе, но все еще довольно хорошо протестирован, так как я использовал его в последние годы для исследований в комбинаторной оптимизации (например, в BBMC, состоянии художественный точный алгоритм максимальной клики). Сравнение с другими хорошо известными реализациями С++ (STL или BOOST) можно найти здесь.

Надеюсь, вы сочтете это полезным. Любая обратная связь приветствуется.

Ответ 9

В развитии микроконтроллера несколько раз нам нужно использовать 2-мерная матрица (матрица) со значением элемента только [0, 1]. Что означает, что если мы используем 1 байт для типа элемента, он сильно выделяет память (память микроконтроллера очень ограничена). Предлагаемое решение что мы должны использовать 1 битовую матрицу (тип элемента - 1 бит).

http://htvdanh.blogspot.com/2016/09/one-bit-matrix-for-cc-programming.html