[Algorithm] Bit와 BitMask (java)

백준 문제를 풀다가 비트마스킹 부분이 나왔다.

배운적이 없기에 다른 블로그를 찾아가며 공부하고 이해한 내용을 정리해보았다.

https://loosie.tistory.com/238

[알고리즘] 비트(Bit)와 비트마스크(BitMask) 정리 (Java)

---

비트(bit; Binary digit): 데이터를 나타내는 최소단위로 이진수(0 | 1)의 값을 가짐.

---

표현할 수 있는 값의 범위 : 2^0 ~ 2^N-1           

*2^0: 최하위 비트(LSB; Least Significant Bit) 

*2^N-1 : 최상위 비트(MSB: Most Significant Bit)

비트 연산자(java)

구분	연산자	뜻	설명
비트연산자	&	AND	모두 1이면 1, 아니면 0 반환
	|	OR	하나라도 1이면 1, 아니면 0 반환
	^	XOR	양쪽이 다르면 1, 같으면 0 반환
	~	NOT	각 비트를 1이면 0, 0이면 1로 바꿈
비트 이동연산자	<<	정수 a를 왼쪽으로 b만큼 이동(빈자리는 0, MSB가 1이면 음수로 바뀜)
	>>	정수 a를 오른쪽으로 b만큼 이동(빈자리 MSB와 같은 값으로 채워짐)
	>>>	정수 a를 오른쪽으로 b만큼 이동(빈자리는 0으로 채워짐)

 

public class Main{
	public static void main(String[] args)throws IOException{
		int x = 10; // 2진수로 변환 : 1010
		int y = 12; // 2진수로 변환 : 1100

		System.out.println("x = \t" + Integer.toBinaryString(x));
		System.out.println("y = \t" + Integer.toBinaryString(y));
		System.out.println("x|y = \t" + Integer.toBinaryString(x|y));
		System.out.println("x&y = \t" + Integer.toBinaryString(x&y));
		System.out.println("x^y = \t" + Integer.toBinaryString(x^y));
		System.out.println("~x = \t" + Integer.toBinaryString(~x));
	}
}

x =     1010
y =     1100
x|y =   1110  // 하나라도 1이면 1
x&y =   1000  // 둘다 1인 경우는 MSB만 존재
x^y =   110   // MSB는 같기에 삭제  
~x =    11111111111111111111111111110101 
//int가 4byte = 32bit So, 1010을 0101로 바꾸고 앞에 28개의 1 출력

---

비트마스크(Bit Mask)

---

 

이진수: 0(Off) & 1 (On) 사용

장점

1. 빠른 수행시간: bit 연산 → 시간복잡도가 O(1)에 구현되는 경우가 많다.
2. 간결한 코드: 다양한 집합연산을 한줄로 작성하여 간결
3. 적은 메모리 사용: bit가 10개인 경우 bit당 2개의 경우를 가지기에 2^10가지 경우를 10bit 이진수로 표현 가능

---

집합 구현

---

집합 구현이 가장 대표적이고 자주 쓰이는 방법이라고 한다.

bit가 1이면 해당 원소가 집합에 포함된 것이고, 0이면 포함되지 않은 것을 의미

 

A를 10개의 집합의 상태를 나타내는 변수라고 가정(0 ~ 9번째 원소)

연산	사용
공집합 & 꽉찬 경우	A = 0;    / A = (1 << 10) -1;
원소 추가	A |= (1 << k);    * 원소에 해당하는 bit만 on해야함 So, bit를 항상 1로 만드는 연산이라 |
원소 삭제	A &= ~(1 << k);  * 이건 이해를 아직 못하겠음;;
원소 포함여부 확인	if((A & (1 << k)) == (1 << k))
원소의 toggle	A ^= (1 << k);
두 집합 연산
A와 B의 합집합	A | B    * | : 하나라도 있으면 1
A와 B의 교집합	A & B   * & : 둘다 존재하면 1
A - B (차집합)	A & (~ B)  * ~ : 0 to 1, 1 to 0
A와 B중 하나에만 포함된 원소들의 집합	A ^ B        * ^ : 양쪽 비트가 다르면 1, 같으면 0 반환
집합 크기 구하기	int bitCount(int A){    if(A == 0) return 0;    return A % 2 + bitCount(A / 2) ; }
최소원소 찾기	int first = A & (-A);
최소원소 삭제	A &= (A - 1);
모든 부분 집합 순회	for( int subset = A; subset > 0; subset = ((subset - 1) & A)) { }

*toggle : 집합 S에 x가 있으면 삭제, 없으면 추가

 

아직 많이 배워야 할 것 같다...

수학적으로 풀고 구현하는 것은 어느정도...? 되는 것 같아서 느낀 것이 메모리 최적화였는데
좋은 알고리즘을 배워가고 더 많이 사용해보고 익혀야겠다.

- fin -