[자료구조] 비트마스크(bitmask)_II

비트연산 활용

1. 모든 부분집합 순회하기

예)  피자의 토핑 종류가 (페페로니,소시지,양파) 라고 하면

{페페로니},{페페로니,소시지},{페페로니,소시지,양파},{소시지},{소시지,양파},{양파} 와 같이 하나 하나 열거하는 경우 다음과 같이 처리

for (int subset = pizza; subset; subset = ((subset-1) & pizza))
{
    //subset 은 pizza의 부분 집합
}
 
 

 

2. 비트마스크를 활용하여 에라토스테네스 체 치기(체치는 메모리를 적게 잡기 때문에 훨씬 더 많은 양의 체를 칠 수 있다.)

#include <iostream>
#include <cstring>
 
#define MAX_N 100000
 
using namespace std;
int n;
unsigned char sieve[(MAX_N + 7) / 8]; // MAX_N 에 7 을 더하는 이유는 MAX_N 이 1이라고 생각하면 이유를 알 수 있다.
//k가 소수인지 판별하는 방법
bool isPrime(int k){
        return sieve[k>>3] & ( 1 << (k & 7)); //k>>3 의 의미는 2의3제곱 8로 나눈 몫의 위치, k & 7 의 의미는 k를 8 로 나눈 나머지
}
//k가 소수가 아니라고 셋팅
inline void setComposite(int k){
        sieve[k>>3] &= ~(1<<(k&7)); //해당 비트만 0 으로 만들어서 & 연산
}
int eratos(){
        memset(sieve,255,sizeof(sieve)); //모든 비트를 1로 셋팅
        setComposite(0);
        setComposite(1);
 
        for(long long i=2; i * i <= n; i++)
        {
            if(isPrime(i))
            {
                //i의 배수 j를 false로 만든다.
                //i*i 미만의 배수는 이미 지워졌다.
                for(long long j = i*i; j<=n; j+=i)
                    setComposite(j);
            }
        }
}
 
int main()
{
    cin >> n;
    eratos();
    for(int i=1;i<=n;i++)
    {
        if(isPrime(i)) cout << i << endl;
    }
 
    return 0;
}

 

3. 0~15 까지의 16개의 숫자 정보 4*4 배열 크기의 정보를 64비트 부호없는 정수형 데이터에 담는 방법

typedef unsigned long long uint64;
 
int get(uint64 mask, int index){
    //mask 의 index 위치에 쓰인 값을 0/1 을 반환한다.
    //(index<<2) 의 의미는 index * 4 의 위치를 찾겠다는 의미
    return (mask >>(index<<2)) & 15;
}
///mask의 index 위치를 value 로 바꾼 결과를 반환 
unsigned long long set(uint64 mask, int index,uint64 value){
    return  mask & ~(15ull << (index<<2)) | (value << (index << 2));
}

index << 2 의 의미는 0~15 까지의 정수를 4비트로 표현이 가능하기 때문에 그만큼 이동한 위치를 찾는 것이다.

4. 어떤 수 S를 N으로 나눈 나머지 구하기

int bitMod(int S,int N)
{
    return S & (N-1);
}
 
int intMod(int S,int N)
{
    return S % N;
}

 

5. 어떤 수 S가 2의 거듭제곱인지 판단하기

bool isPowOf2(int S)
{
    return ((S & (S-1) ) == 0);
}

 

6. 어떤 수 S의 마지막 비트를 꺼라

S & (S-1)

예) 101000 => 100000

 

7. S에서 마지막으로 연달아 나타나는 1을 모두 꺼라.

S & (S+1) 

예) 100111 => 100000

 

이 자료는 학생들과 비트마스크는 무엇이고 어떻게 사용되는지 알아 보기 위해 작성된 문서입니다.

 

오늘도 최선을 다하는 우리 학생들을 응원합니다.

 

인천 서구 검단신도시 원당컴퓨터학원