본문 바로가기

프로그래밍/알고리즘/C++

[C++] 비트 마스크 배열 (큰 비트 마스크)

#include <stdio.h>

#include <intrin.h> //gcc 경우 해제

#include <string.h>

#define SIZE 3

#define BLOCK 32

 

//모두 끄기

inline void clear(int *bitmask){

   memset(bitmask,0,sizeof(bitmask));

}

 

//n 비트 켜졌는지

inline int isOn(int *bitmask,int n){

   return (bitmask[n/BLOCK]&(1<<n%BLOCK))!=0;

}

//n 비트 켜기

inline void turnON(int *bitmask,int n){

   bitmask[n/BLOCK]|=(1<<n%BLOCK);

}

//n 비트 끄기

inline void turnOff(int *bitmask,int n){

   bitmask[n/BLOCK]&=~(1<<n%BLOCK);

}

 

//  토글

inline void toggle(int *bitmask,int n){

   bitmask[n/BLOCK]^=(1<<n%BLOCK);

}

 

//범위 토글

void toggle_range(int *bitmask,int begin,int amount){

   int end=begin+amount-1;

   //begin end 같은 블럭내 연산이면

   if(begin/BLOCK==end/BLOCK){

       bitmask[begin/BLOCK]^=(~0<<(begin%BLOCK))&~(~0<<(end%BLOCK)<<1);

       return;

   }

   //서로 다른 블럭이면.

   bitmask[begin/BLOCK]^=(~0<<(begin%BLOCK));

   for(int i=begin/BLOCK+1;i<end/BLOCK;i++)

       bitmask[i]^=~0;

   bitmask[end/BLOCK]^=~(~0<<(end%BLOCK)<<1);

}

 

//켜진 비트 카운터

int popcnt(int *bitmask) {

   int sum = 0;

   for (int i = 0i < SIZE; i++)

       sum += __popcnt(bitmask[i]);  //gcc 경우 __builtin_popcount

   return sum;

}

 

int main() {

   unsigned int bitmask[SIZE] = { 0 };

   toggle_range(bitmask,0,64);

   for(int i=SIZE*BLOCK-1;i>=0;i--)

       printf("%d",isOn(bitmask,i));

   printf("\n개수: %d\n"popcnt(bitmask));

 

}


비트마스크 기본 사용법: http://sunnyholic.com/88


define된 SIZE를 조정하여 SIZE*BLOCK 크기의 큰 비트 마스크를 만들 수 있다.


unsigned int 형으로 써줘야 합니다.