비트 연산

오랜만에 포스팅이다.
오늘은 비트연산을 이용해서 재귀의 방문처리를 해보았다.
사실 전혀 모르던 개념은 아니지만... 실제로 적용할려는 생각을 해본적이 없ㄴ는 것 같다. 굳이? 라는 생각이 컸다. 언제까지 피할 수는 없으니... 지금이라도 정리해놓고 조금씩 숙련도를 높혀가야 겠다는 생각이 들기도 하고, 금방 까먹을까 싶어 기록하고자 한다!

비트 연산자

• & ( AND )
  - AND연산은 비교 두 비트가 모두 1이면 1
• | ( OR )
  - OR연산은 비교 두 비트가 하나라도 1이면 1
• ^ ( XOR )
  - Exclusive OR 연산
  - 비교 두 비트가 같으면 1 다르면 0
• ~ ( NOT )
  - 비트를 반전시킨다 ( 1은 0으로 0은 1로 )
  - 단항연산
• <<, >> (SHIFT)
  - 비트를 해당 방향으로 밀어낸다.

비트를 이용한 boolean 처리

• visited[3] = true -> visit|(1<<3)
• visited[3] = false -> visit&~(1<<3)
• if(visited[3]) -> if((visit&(1<<3)!=0)

적용

아래는 기존에 풀었던 백준 2961 번 문제에서 작성했던 부분집합 재귀이다.
아래 코드를 비트마스킹을 통해서 개선해보자.

static void sub(int cnt) {
	if (cnt == N) {
		boolean allFalse = true;
		for (int i = 0; i < N; i++) {
			if (isSelected[i]) {
				allFalse = false;
			}
		}
		if (allFalse) return;

		int sour = 1;
		int bitter = 0;
		for (int h = 0; h < N; h++) {
			if (isSelected[h]) {
				sour *= things[h][0];
				bitter += things[h][1];
			}
		}
		int temp = Math.abs(sour - bitter);
		result = Math.min(temp, result);

		return;
	}

	isSelected[cnt] = true;
	sub(cnt + 1);
	isSelected[cnt] = false;
	sub(cnt + 1);
}

앞에서 기입했던 방식으로 isSelected 부분을 bit 변수 한개로 관리하도록 변경.

static void sub(int cnt) {

	if (cnt == N) {
		boolean allFalse = true;
		for (int i = 0; i < N; i++) {
			if ((bit & (1 << i)) != 0) {
				allFalse = false;
			}
		}
		if (allFalse)
			return;

		int sour = 1;
		int bitter = 0;
		for (int h = 0; h < N; h++) {
			if ((bit & (1 << h)) != 0) {
				sour *= things[h][0];
				bitter += things[h][1];
			}
		}
		int temp = Math.abs(sour - bitter);
		result = Math.min(temp, result);

		return;
	}

	bit = bit | (1 << cnt);
	sub(cnt + 1);
	bit = bit & ~(1 << cnt);
	sub(cnt + 1);
}

true처리와 false처리가 아직 햇갈려서 재귀코드를 변경 적용할 때 답이 틀리게 나왔다.
익숙해지도록 다음 알고리즘 문제에서 조금씩 적용해보자!