[알고리즘] Bit Masking

 

 

 Bit Masking 

개요

보통 알고리즘 문제를 풀 때 방문했다는 표시로 boolean visit 배열을 많이 사용합니다.

BitMask 은 해당 visit 배열처럼 bit 표현을 통해서 true/false 를 표시하는 기법이라고 보시면 됩니다.

 

방문을 했다 → true, 1
방문을 하지 않았다 → false, 0

bit 자체가 0, 1 을 통해 표시가 되니 visit 배열과 방식의 차이가 없어 쉬이 이해가 되실겁니다.

저도 처음에 이게 무슨 소린가 싶었는데 bit 표현만 생각해보면 이해가 되는 것이었습니다.

이해가 안되신다면 아래 설명을 확인해주시길 바랍니다.

 

 

bit 표현

public class Test {

	public static void main(String[] args) throws Exception {
		int n1 = 1 << 1;
		int n2 = 1 << 2;
		int n3 = 1 << 3;

		System.out.println(n1);
		System.out.println(Integer.toBinaryString(n1));

		System.out.println(n2);
		System.out.println(Integer.toBinaryString(n2));

		System.out.println(n3);
		System.out.println(Integer.toBinaryString(n3));
	}
}

출력

bit 연산에서 left shift 를 하면 비트가 한 칸 왼쪽으로 이동합니다.

이는 마치 x2 가 되는 것과 같습니다. 이진수에서는 한 칸 왼쪽으로 이동하는 것이 십진수에서는 x2 를 하는 것과 마찬가지지요.

즉슨 1 << 2 라면 2 인덱스 자리가 방문 처리가 되는 것이고, 1 << 3 라면 3 인덱스 자리가 방문 처리가 되는것이지요.

 

 

visit 표현: 방문 처리

public class Test {

	public static void main(String[] args) throws Exception {
		// visit = {true, false, true, false}; 라는 배열을 표현하고 싶다면
		int visit = 0;
		System.out.println("1st: " + visit);
		System.out.println(Integer.toBinaryString(visit));

		visit = visit | 1 << 1;
		System.out.println("2nd: " + visit);
		System.out.println(Integer.toBinaryString(visit));

		visit = visit | 1 << 3;
		System.out.println("3rd: " + visit);
		System.out.println(Integer.toBinaryString(visit));
	}
}

출력

만약 일차원 배열이 있다고 할 때, 아래와 같이 index 0번째와 2번째를 true 로 방문처리를 하고싶다고 가정해봅시다.

visit = {true, false, true, false};

그러면 여기서 주의할 점은 배열은 왼쪽부터 0, 1, 2, 3.. 이렇게 인덱스가 매겨지지만

이진수는 오른쪽부터 .. 3, 2, 1, 0 이렇게 매겨집니다. 따라서 자리를 확인하고 싶다면 오른쪽부터 세야겠죠?

 

이렇게 줄 글로 표현하자니 어려워 보이긴 하는데 (참 저도 헷갈리네요) 별 거 없습니다.

그냥 오른쪽부터 숫자를 세서 0번째 2번째에 인덱스에 해당하는 1, 3 번째 자리를 left shift 하면 됩니다.

visit | (1 << 1); 이런식으로 봐주세요.

 

visit | (1 << 1)
visit: 0
1 << 1 : 10
→ 0 | 10
→ 10

visit | (1 << 3)
visit: 2 (10)
1 << 3: 1000
→ 10 | 1000
→ 1010

visit 처리를 하고 싶다면 그렇담 OR 연산을 하면 됩니다. 비트 or 연산은 java 에서 | 기호를 이용해 사용할 수 있습니다.

 

 

visit 표현: 방문 확인

그렇다면 방문 확인같은 것은 어떻게 할 수 있을까요?

이때는 & 연산을 사용하면 됩니다.

 

public class Test {

	public static void main(String[] args) throws Exception {
		// visit = {true, false, true, false}; 라는 배열을 표현하고 싶다면
		int visit = 10;
		System.out.println(visit);
		System.out.println(Integer.toBinaryString(visit));
		System.out.println();

		int check1 = visit & (1 << 1);
		System.out.println("1st: " + check1 + " " + (check1 != 0));
		System.out.println(Integer.toBinaryString(check1));

		int check2 = visit & (1 << 2);
		System.out.println("2nd: " + check2 + " " + (check2 != 0));
		System.out.println(Integer.toBinaryString(check2));

		int check3 = visit & (1 << 3);
		System.out.println("3rd: " + check3 + " " + (check3 != 0));
		System.out.println(Integer.toBinaryString(check3));

	}
}

출력

AND 연산으로 해당 자리에 1이 있는지 아닌지 확인할 수 있습니다.

만약 있다면 0이 아닌 수가 리턴이 되고, 없다면 0이 리턴이 됩니다.

따라서 만약 visit check 를 하고 싶다면

해당 문장과 같이 visit & (1 << 2); 이런식으로 0을 리턴하는지 아닌지 boolean check 를 하여 확인할 수 있을 것입니다.

 

 

 

 

 

 

 

 

 

# 알고리즘 Bit Masking # 알고리즘 BitMask 개념 # 알고리즘 Bit Masking visit check # 알고리즘 비트마스킹 java

---