[자바] 비트마스킹 / 비트연산자 (&, |, ^, ~, >>, <<)

비트마스킹/ 비트연산자

1. 비트마스킹(bitmasking)

• 비트(bit)는 0과 1 값을 가지는 이진 숫자이며, true/false , on/off 상태를 나타낸다.
• 이런 특성을 가진 비트를 이용해 자료구조로 쓰는 기법을 비트 마스킹이라 한다.
• 장점 : 빠른 수행 시간, 간결한 코드, 적은 메모리 사용
• 단점 : 인라인 함수가 길거나 호출하는 경우가 잦으면 컴파일된 코드가 더 길어질 수도 있다

비트마스크 적용 전

boolean featureA = true;
boolean featureB = false;
boolean featureC = true;
boolean featureD = false;

이 경우에는 4개의 boolean 변수를 사용하여 각 기능의 상태를 나타낸다. 이 방식은 일반적으로 각 boolean 변수에 최소 1바이트의 메모리가 필요하므로 메모리 사용량 측면에서 비효율적일 수 있다.

비트마스크 적용 후

int featureStatus = 0; //모든 Feature disable로 초기화

//비트마스크를 사용하여 Feature 사용
featureStatus |= (1 << 0); // Feature A (bit 0)
featureStatus |= (1 << 2); // Feature C (bit 2)

//비트마스크를 사용하여 각 Feature가 사용됐는지 확인
boolean isFeatureAEnabled = ((featureStatus & (1 << 0)) != 0); // FeatureA 확인
boolean isFeatureBEnabled = ((featureStatus & (1 << 1)) != 0); // FeatureB 확인
boolean isFeatureCEnabled = ((featureStatus & (1 << 2)) != 0); // FeatureC 확인
boolean isFeatureDEnabled = ((featureStatus & (1 << 3)) != 0); // FeatureD 확인

비트 연산을 사용하여 각 기능의 상태를 활성화, 비활성화를 확인할 수 있다. "<<"는 특정 비트를 설정하는 데 사용되며 비트 &는 개별 비트의 상태를 확인하는 데 사용한다.

 

2. 비트연산자

연산	사용 예시
공집합과 꽉 찬 집합 구하기	A = 0; / A = (1 << 10) - 1;
원소 추가	A |= (1 << k);
원소 삭제	A &= ~(1 << k);
원소의 포함 여부 확인	if((A & (1 << k)) == (1 << k))
원소의 토글(toggle)	A ^= (1 << k);
두 집합에 대해서 연산	A | B       → A와 B의 합집합 A & B     → A와 B의 교집합 A & (~B) → A에서 B를 뺀 차집합 A ^ B     → A와 B중 하나에만 포함된 원소들의 집합
집합의 크기 구하기	int bitCount(int A){   if(A == 0) return 0;   return A%2 + bitCount(A / 2); } [내장 명령어] gcc/g++ → __builtin_popcount(A)  visual C++ → __popcnt(A) Java → Integer.bitCount(A)
최소 원소 찾기	int first = A & (-A);
최소 원소 지우기	A &= (A - 1);
모든 부분 집합 순회하기	for (int subset = A ; subset>0; subset = ((subset - 1) & A)){ }

비트 연산자	설명
~	비트를 1이면 0으로, 0이면 1로 반전시킴. (비트 NOT 연산)
&	대응되는 비트가 모두 1이면 1을 반환함. (비트 AND 연산)
|	대응되는 비트 중에서 하나라도 1이면 1을 반환함. (비트 OR 연산)
^	대응되는 비트가 서로 다르면 1을 반환함. (비트 XOR 연산)
<<	지정한 수만큼 비트들을 전부 왼쪽으로 이동시킴. (left shift 연산)
>>	지정한 수만큼 비트들을 전부 오른쪽으로 이동시킴. (right shift 연산)

비트마스킹 관련 백준 문제

1. [실버5] 집합

11723번: 집합

2. [실버5] 막대기

1094번: 막대기

3. [실버4] 비트가 넘쳐흘러

17419번: 비트가 넘쳐흘러