[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 = 0; i < 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 형으로 써줘야 합니다.

저작자표시비영리변경금지

• 카카오스토리
• 트위터
• 페이스북

'프로그래밍/알고리즘 > C++' 카테고리의 다른 글

[C++] 구간트리 (Binary Indexed Tree) - 구간 최대,최소값  (1)	2015.08.12
[C++] 펜윅트리 (이진 인덱스 트리) - 구간합 구해주는 트리  (0)	2015.07.28
[C++] 비트 마스크 배열 (큰 비트 마스크)  (0)	2015.07.27
트리 최적 노드 삽입 순서  (0)	2015.07.09
버블 정렬 알고리즘 오름차순  (0)	2015.07.08
[C++] 창작 스도쿠 푸는 알고리즘  (0)	2015.07.06