[비트연산] 비트연산자 & 비트마스크

 

 

아주 쉬운 연습문제 : https://www.acmicpc.net/problem/11723

11723번: 집합

문제 풀이는 여기!

2019/08/06 - [PS/백준 문제풀이] - [백준 11723] 집합

[백준 11723] 집합

 

---

 

집합 구하기

// 꽉 찬 집합 구하기
// 각 비트가 0~size 까지의 수를 나타냄.
int fullBits = (1 << size+1) - 1;

// 공집합
int zeroBits = 0;

 

비트 연산

// p 자리에 원소 추가
bits |= (1 << p);

// p 자리 원소 포함 여부 확인
// 자리 확인의 결과값은 0 또는 1<<p 값임. 무조건 1이 아님.
if(bits & (1 << p))
	cout << "yes!" << endl;
    
// p 자리 원소 삭제
bits &= ~(1 << p);

// p 자리 원소 토글 (on <-> off)
bits ^= (1 << p);

 

집합 크기 구하기 -- > 내장 명령어를 사용하자! (언더바(_)는 2개씩)

컴파일러 혹은 언어	집합 크기 구하기
gcc/g++	__builtin_popcount(bits)
Visual C++	__popcnt(bits)
Java	Integer.bitCount(bits)

 

 

최소 원소 찾기 -- > 내장 명령어를 사용하자! (언더바(_)는 2개씩)

컴파일러 혹은 언어	최소 원소 찾기
gcc/g++	__builtin_ctz(bits)
Visual C++	__BitScanForward(&index, bits)
Java	Integer.numberOfTrailingZeros(bits)

 

최하위 비트의 번호 대신 (최소원소의 자리) 해당 비트를 직접 구하고 싶은 경우.

예를 들어) 40일 때 0010 1000 에서 3대신 2^3 == 8 을 구하고 싶을 때.

int firstNum = (bits & -bits)

 

최소 원소 지우기 (거듭제곱 확인 가능)

bits &= (bits-1);

최소 원소를 지우는 방식인데 이 연산 후의 bits값이 0이면 bits는 2의 거듭제곱임.

 

 

모든 부분집합 순회하기

for(int subset = bits; subset; subset = (subset-1 & bits)){
	.....
}