비트마스크

<오버플로우 주의>

1은 부호있는 32비트 상수취급이므로

(1<<31)부터 에러가 난다

(1ll<<31) 혹은 (1ull<<31) 혹은 ((ll)1<<31)등의 방법을 쓰자

 

<기본>

집합 a,b에 대해

1. p번 요소 삭제 : a &= ~(1<<p)

2. p번 요소 토글 : a ^= (1<<p)

3. 합집합 : added = a|b

4. 교집합 : inter = a&b

5. a-b(차집합) : removed = a & ~b

 

<비트 개수>

vs : __popcnt(s)

gcc : __bulitin_popcount(s)

 

<최하위 원소 찾기>

집합에 포함된 가장 작은 인덱스를 반환.

(정수 s의 이진수 표현에서 오른쪽 끝에 붙어있는 0이 몇개인지 반환.)

vs : _BitScanForward(&index, s) 

gcc : __builtin_ctz(s)  ->s==0일때 정의돼있지 않다. 주의

 

해당 비트를 직접 구하고 싶다면? 예를들어 101000에서 3대신 2^3을 구하는 법

int f = (s & -s);

-> -s는 s의 보수+1이므로 해당 비트왼쪽으론 모두 다르고 오른쪽으로 둘다 0임. 손으로 써보자.

->펜윅트리에서 유용하게 사용

 

 

<최하위 원소 지우기> ~2의 거듭제곱 값인지 확인

s &= (s-1);

s-1의 이진수 표현은 s의 최하위 비트를 끄고 그 밑의 비트들은 전부 켠 것.

 

2의 거듭제곱은 켜진 비트가 하나이므로 최하위 비트를 지우면 0이된다.

 

 

<모든 부분집합 순회하기>

여태 문제풀땐 보통 total = 2^n-1꼴이라 증감식부분이 subset--로 충분했다.

total != 2^n-1꼴이 아닐 때를 포함한 일반적인 표현은 다음과 같다.

for(int subset = total; subset; subset = ((subset-1)&total)){
	///
}

 

 

<에라토스테네스의 체>

일반적인 방법으로 한다면 불린형 배열에, 32비트 정수가 표현할 수 있는 범위 내의 모든 수에 대해서

(2^32-1) * 1byte(4기가)의 메모리가 필요하다. (불린형 크기 1byte. char과 같다)

 

이를 담을 배열의 타입을 다음과 같이 바꾸면 대충 2^29 바이트(0.5기가)로 줄일 수 있다.

unsigned char era[(MAX+7)/8];

 

k번쨰 원소가 소수인지 알기 위해선 era[k/8]의 k%8번째 비트가 켜져있는지 확인하면 된다.

 

(1<<(k&7))  =>  k%8

const unsigned int MAX = (1<<31)-1;

int n;
unsigned char era[(MAX + 7) / 8];

//k가 소수인지 확인
inline bool isPrime(int k) {
	return era[k >> 3] & (1 << (k & 7));
}
//k는 소수가 아니라고 표기
inline void setComposite(int k) {
	era[k >> 3] &= ~(1 << (k & 7));
}

void eratos() {
	memset(era, 255, sizeof(era));
	setComposite(0);
	setComposite(1);
	for (ll i = 2; i * i <= n; i++) {
		if (isPrime(i))
			for (ll j = i * i; j <= n; j += i)
				setComposite(j);
	}
}