C의 비트 배열 정의 및 조작 방법

C의 비트 배열 정의 및 조작 방법

0과 1을 쓸 수 있는 매우 큰 배열을 만들고 싶습니다.저는 무작위 순차 흡착이라고 불리는 물리적 과정을 시뮬레이션하려고 합니다. 길이 2의 단위인 이합체가 서로 겹치지 않고 임의의 위치에 있는 n차원 격자에 쌓이는 것입니다.격자 위에 더 많은 이합체를 쌓을 공간이 없어지면(라티스가 막힘) 프로세스가 중지됩니다.

처음에는 0의 격자로 시작하고, 이합체는 '1' 쌍으로 표시됩니다.각 조광체가 퇴적될 때 조광체 좌측의 부위는 겹칠 수 없기 때문에 차단된다.그래서 저는 격자 위에 '1'의 3배를 적어서 이 과정을 시뮬레이트합니다.전체 시뮬레이션을 여러 번 반복한 후 평균 커버리지 %를 계산해야 합니다.

이미 1D 및 2D 격자에 대해 여러 가지 문자를 사용하여 이 작업을 완료했습니다.현재 저는 3D 문제와 더 복잡한 일반화에 앞서 코드를 최대한 효율적으로 만들려고 노력하고 있습니다.

기본적으로 코드는 다음과 같습니다. 단순화된 1D 형식입니다.

int main()
{
    /* Define lattice */
    array = (char*)malloc(N * sizeof(char));

    total_c = 0;

    /* Carry out RSA multiple times */
    for (i = 0; i < 1000; i++)
        rand_seq_ads();

    /* Calculate average coverage efficiency at jamming */
    printf("coverage efficiency = %lf", total_c/1000);

    return 0;
}

void rand_seq_ads()
{
    /* Initialise array, initial conditions */
    memset(a, 0, N * sizeof(char));
    available_sites = N;
    count = 0;

    /* While the lattice still has enough room... */
    while(available_sites != 0)
    {
        /* Generate random site location */
        x = rand();

        /* Deposit dimer (if site is available) */
        if(array[x] == 0)
        {
            array[x] = 1;
            array[x+1] = 1;
            count += 1;
            available_sites += -2;
        }

        /* Mark site left of dimer as unavailable (if its empty) */
        if(array[x-1] == 0)
        {
            array[x-1] = 1;
            available_sites += -1;
        }
    }

    /* Calculate coverage %, and add to total */
    c = count/N
    total_c += c;
}

실제 프로젝트에서는 조광기뿐만 아니라 트리머, 쿼드라이머 및 모든 종류의 모양과 크기(2D 및 3D용)가 사용됩니다.

바이트가 아닌 개별 비트로 작업할 수 있으면 좋겠다고 생각했습니다만, 지금까지 읽어 본 결과, 한 번에 변경할 수 있는 것은 1바이트뿐이므로, 복잡한 인덱싱을 해야 합니까, 아니면 간단한 방법이 있습니까?

답변 감사합니다.

제가 너무 늦지 않았다면 이 페이지는 예시와 함께 멋진 설명을 해 줍니다.

int일련의 처리에 사용할 수 있다bits를 가정하면.int4 bytes에 int 우리는 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , .32 bits 이렇게 '있다'가 있다'고 해 .int A[10] , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,10*4*8 = 320 bits각큰 블록이 , 각은 a(즉, 4개의 블록)를 .byte그리고 작은 블록은 각각을 나타냅니다.bit)

설정하기 k 내의 "th"A:

// NOTE: if using "uint8_t A[]" instead of "int A[]" then divide by 8, not 32
void  SetBit( int A[],  int k )
{
    int i = k/32;        //gives the corresponding index in the array A
    int pos = k%32;      //gives the corresponding bit position in A[i]

    unsigned int flag = 1;   // flag = 0000.....00001

    flag = flag << pos;      // flag = 0000...010...000   (shifted k positions)

    A[i] = A[i] | flag;      // Set the bit at the k-th position in A[i]
}

또는 단축판입니다.

void  SetBit( int A[],  int k )
{
    A[k/32] |= 1 << (k%32);  // Set the bit at the k-th position in A[i]
}

k 비트th번째 비트:

void  ClearBit( int A[],  int k )                
{
    A[k/32] &= ~(1 << (k%32));
}

하는 k 비트th번째 비트:

int TestBit( int A[],  int k )
{
    return ( (A[k/32] & (1 << (k%32) )) != 0 ) ;     
}

상기와 같이, 이러한 조작은 매크로로서도 쓸 수 있습니다.

// Due order of operation wrap 'k' in parentheses in case it
// is passed as an equation, e.g. i + 1, otherwise the first
// part evaluates to "A[i + (1/32)]" not "A[(i + 1)/32]"
#define SetBit(A,k)     ( A[(k)/32] |= (1 << ((k)%32)) )
#define ClearBit(A,k)   ( A[(k)/32] &= ~(1 << ((k)%32)) )
#define TestBit(A,k)    ( A[(k)/32] & (1 << ((k)%32)) )

typedef unsigned long bfield_t[ size_needed/sizeof(long) ];
// long because that's probably what your cpu is best at
// The size_needed should be evenly divisable by sizeof(long) or
// you could (sizeof(long)-1+size_needed)/sizeof(long) to force it to round up

여기서 bfield_t의 각 길이는 8비트의 크기를 유지할 수 있습니다.

필요한 큰 인덱스는 다음 방법으로 계산할 수 있습니다.

bindex = index / (8 * sizeof(long) );

비트번호는 다음과 같습니다.

b = index % (8 * sizeof(long) );

그런 다음 필요한 시간을 찾아보고 필요한 부분을 숨길 수 있습니다.

result = my_field[bindex] & (1<<b);

또는

result = 1 & (my_field[bindex]>>b); // if you prefer them to be in bit0

첫 번째 CPU는 일부 CPU에서 더 빠를 수 있습니다.또한 여러 비트 어레이에서 같은 비트 간에 작업을 수행해야 하는 번거로움을 줄일 수 있습니다.또한 두 번째 구현보다 현장에서 비트의 설정과 클리어도 더 밀접하게 반영됩니다.설정:

my_field[bindex] |= 1<<b;

클리어:

my_field[bindex] &= ~(1<<b);

필드를 유지하는 롱에서 비트 연산을 사용할 수 있으며 이는 개별 비트의 연산과 동일합니다.

(사용 가능한 경우)에 이 좋습니다.ffs, fls, ffc flc flc는 ffs에서 항상 할 수 있어야 .strings.h을 사용하다일련의 비트입니다.이치노력하다

int ffs(int x) {
    int c = 0;
    while (!(x&1) ) {
        c++;
        x>>=1;
    }
    return c; // except that it handles x = 0 differently
}

이것은 프로세서에 명령어가 있는 일반적인 조작이며, 컴파일러는 제가 쓴 것과 같은 함수를 호출하는 것이 아니라 명령어를 생성할 것입니다.참고로 x86은 이에 대한 지침을 가지고 있습니다.아, ffsl과 ffsl은 각각 long과 long이 걸리는 것을 제외하고는 동일한 기능입니다.

&(비트 및) 및 <<(왼쪽 시프트)를 사용할 수 있습니다.

예를 들어, (1 < 3)을 지정하면, 바이너리로 「00001000」이 됩니다.따라서 코드는 다음과 같습니다.

char eightBits = 0;

//Set the 5th and 6th bits from the right to 1
eightBits &= (1 << 4);
eightBits &= (1 << 5);
//eightBits now looks like "00110000". 

그런 다음 문자 배열로 크기를 조정하고 먼저 수정할 적절한 바이트를 구하십시오.

효율성을 높이기 위해 비트필드 목록을 미리 정의하고 배열에 넣을 수 있습니다.

#define BIT8 0x01
#define BIT7 0x02
#define BIT6 0x04
#define BIT5 0x08
#define BIT4 0x10
#define BIT3 0x20
#define BIT2 0x40
#define BIT1 0x80

char bits[8] = {BIT1, BIT2, BIT3, BIT4, BIT5, BIT6, BIT7, BIT8};

그런 다음 비트 이동의 오버헤드를 방지하고 비트를 인덱싱하여 이전 코드를 다음과 같이 변환할 수 있습니다.

eightBits &= (bits[3] & bits[4]);

C 를 할 수 있는 는, 「C++」를 할 수도 .std::vector<bool>이는 내부적으로 비트의 벡터로 정의되며 직접 인덱싱이 완료됩니다.

비트 어레이h:

#include <inttypes.h> // defines uint32_t

//typedef unsigned int bitarray_t; // if you know that int is 32 bits
typedef uint32_t bitarray_t;

#define RESERVE_BITS(n) (((n)+0x1f)>>5)
#define DW_INDEX(x) ((x)>>5)
#define BIT_INDEX(x) ((x)&0x1f)
#define getbit(array,index) (((array)[DW_INDEX(index)]>>BIT_INDEX(index))&1)
#define putbit(array, index, bit) \
    ((bit)&1 ?  ((array)[DW_INDEX(index)] |= 1<<BIT_INDEX(index)) \
             :  ((array)[DW_INDEX(index)] &= ~(1<<BIT_INDEX(index))) \
             , 0 \
    )

용도:

bitarray_t arr[RESERVE_BITS(130)] = {0, 0x12345678,0xabcdef0,0xffff0000,0};
int i = getbit(arr,5);
putbit(arr,6,1);
int x=2;            // the least significant bit is 0
putbit(arr,6,x);    // sets bit 6 to 0 because 2&1 is 0
putbit(arr,6,!!x);  // sets bit 6 to 1 because !!2 is 1

문서를 편집합니다.

"dword" = "double word" = 32비트 값(지정되지 않았지만 그다지 중요하지 않음)

RESERVE_BITS: number_of_bits --> number_of_dwords
    RESERVE_BITS(n) is the number of 32-bit integers enough to store n bits
DW_INDEX: bit_index_in_array --> dword_index_in_array
    DW_INDEX(i) is the index of dword where the i-th bit is stored.
    Both bit and dword indexes start from 0.
BIT_INDEX: bit_index_in_array --> bit_index_in_dword
    If i is the number of some bit in the array, BIT_INDEX(i) is the number
    of that bit in the dword where the bit is stored.
    And the dword is known via DW_INDEX().
getbit: bit_array, bit_index_in_array --> bit_value
putbit: bit_array, bit_index_in_array, bit_value --> 0

getbit(array,i)비트 i가 포함된 dword를 가져오고 dword를 오른쪽으로 이동하면 비트 i가 최하위 비트가 됩니다.그런 다음 비트 단위로 1을 지정하면 다른 모든 비트가 지워집니다.

putbit(array, i, v)우선 v의 최하위 비트를 확인합니다.v가 0이면 비트를 클리어하고 1이면 비트를 설정해야 합니다.
비트를 설정하려면 비트 단위 또는 비트를 포함하는 dword와 bit_index_in_dword 왼쪽 1의 값을 수행합니다.이 비트는 설정되며 다른 비트는 변경되지 않습니다.
비트를 클리어하려면 비트 및 비트를 포함하는dword와 bit_index_in_dword 왼쪽의 비트 보수가1로 설정됩니다.이 값은 클리어하는 위치에 있는 유일한0 비트를 제외한 모든 비트가1로 설정됩니다.
매크로의 끝은 다음과 같습니다., 0그렇지 않으면 비트 i가 저장되어 있는 dword 값이 반환되어 의미가 없기 때문입니다.또,((void)0).

이것은 트레이드오프입니다.

(1) 각 2비트 값에 대해 1바이트 사용 - 단순하고 빠르며 4배의 메모리를 사용합니다.

(2) 비트를 바이트 단위로 팩 - 보다 복잡하고 퍼포먼스 오버헤드가 있으며 최소한의 메모리를 사용합니다.

충분한 메모리가 있는 경우는, (1)로 해 주세요.그렇지 않은 경우는 (2)로 해 주세요.

언급URL : https://stackoverflow.com/questions/2525310/how-to-define-and-work-with-an-array-of-bits-in-c