C/C++ 효율적 비트 배열

C/C++ 효율적 비트 배열

임의 길이 비트 배열을 조작하는 효율적/깨끗한 방법을 추천해 주시겠습니까?

현재 일반 int/char 비트 마스크를 사용하고 있지만 배열 길이가 데이터 유형 길이보다 클 경우에는 그다지 깨끗하지 않습니다.

std vector<bool>저는 이용할 수 없습니다.

만 아니라 C++도C++와 같은 은 C+++ 까지하셨으니 C++ 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 *매개 변수. 의 수명할 수 방법은 아직이 입니다.비트 집합의 수명 동안 크기를 조정할 수 있는 방법은 여전히 없으며 경계 검사도 없지만 이 시점에서 추가하기는 어려울 것입니다.

boost::dynamic_bitset 런 타임(run time)에서만 길이를 알 수 있는 경우.

std::bitset 컴파일 시간에 길이를 알 수 있는 경우(임의적이긴 하지만).

C(BSD license)에서 비트 배열을 제공하라는 Dale Hagglund의 응답을 바탕으로 작업 구현을 작성했습니다.

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

어떻게 생각하시는지 알려주시기 바랍니다.이 질문에 대한 답변을 찾으시는 분들이 유용하게 생각하셨으면 좋겠습니다.

이 포스팅은 꽤 오래된 것이지만, 내 ALFLB 라이브러리의 C에 효율적인 비트 어레이 제품군이 있습니다.

하드웨어 분할 opcode가 없는 많은 마이크로컨트롤러의 경우, 이 라이브러리는 분할을 사용하지 않기 때문에 효율적입니다. 대신 마스킹과 비트 시프트가 사용됩니다.(네, 일부 컴파일러는 분할을 8씩 시프트로 변환하는 것으로 알고 있지만, 이것은 컴파일러마다 다릅니다.)

최대 2^32-2비트(536MB바이트에 저장된 약 40억 비트)의 어레이에서 테스트되었지만, 애플리케이션에서 포루프를 사용하지 않는 경우에는 마지막 2비트에 액세스할 수 있어야 합니다.

문서에서 발췌한 내용은 아래를 참조하십시오.Docois http://alfredo4570.net/src/alflb_doco/alflb.pdf, 라이브러리는 http://alfredo4570.net/src/alflb.zip 입니다.

즐거운 시간 되세요.
알프

//------------------------------------------------------------------
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.
//------------------------------------------------------------------

std::비트셋을 사용할 수 있습니다.

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;
  }
}

오래된 게시물인 것은 알지만 간단한 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;
}

나는 이것을 사용합니다.

//#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))

저는 최근 빠른 비트 스캔 작업을 지향하는 C++ 비트열 라이브러리인 BITSCAN을 출시했습니다.비츠캔은 여기서 이용 가능합니다.그것은 알파에 있지만 최근 몇 년 동안 조합 최적화 연구에 사용했기 때문에 여전히 꽤 잘 테스트되었습니다(예: BBMC, 최첨단 최대 클라이크 알고리즘).잘 알려진 다른 C++ 구현(STL 또는 BOOST)과의 비교는 여기에서 확인할 수 있습니다.

유용하게 쓰이길 바랍니다.어떤 피드백이든 환영합니다.

마이크로 컨트롤러 개발에서 요소 값이 [0, 1]인 2차원 배열(매트릭스)을 사용해야 할 때가 있습니다.즉, 요소 유형에 1바이트를 사용하면 메모리가 크게 낭비됩니다(마이크로 컨트롤러의 메모리는 매우 제한적임).제안된 해결책은 1비트 행렬(element type은 1비트)을 사용해야 한다는 것입니다.

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

이를 위해 최근 BitContainer라는 작은 헤더 전용 라이브러리를 구현했습니다.표현력과 컴파일 타임 능력에 초점을 맞추고 있으며 여기에서 https://github.com/EddyXorb/BitContainer 를 확인할 수 있습니다.

비트 어레이를 보는 고전적인 방법은 아니지만 강력한 타이핑 목적과 명명된 속성의 메모리 효율적인 표현을 위해 유용할 수 있습니다.

예:

constexpr Props props(Prop::isHigh(),Prop::isLow()); // intialize BitContainer of type Props with strong-type Prop

constexpr bool result1 = props.contains(Prop::isTiny()) // false
constexpr bool result2 = props.contains(Prop::isLow())  // true

언급URL : https://stackoverflow.com/questions/2633400/c-c-efficient-bit-array