[알고리즘] 비트 마스킹(Bit Masking)

비트 마스킹은 알고리즘이라기 보다는 비트의 연산을 이용한 테크닉이라고 볼 수 있다. &, |, ^등의 비트 연산을 활용하여 정수의 이진 비트를 처리하는 작업이다. 그렇게 많이 사용될 일은 없겠으나, 가끔 사용해야 할 때 비트 마스킹을 사용하면 훨씬 빠르고 간단하게 코드를 구현할 수 있다. 비트 마스킹의 장점은 다음과 같다.

• 메모리를 적게 사용할 수 있다
• 프로그램이 빠르게 동작
• 소스코드가 직관적이게 된다

 

가령 미로를 탈출하는 시뮬레이션에서 코드를 구현할 때, 필요한 열쇠가 6개(a, b, c, d, e, f)라고 하자. 현재 이 중에 어떤 열쇠를 갖고 있는지를 어떻게 저장할 것이며, 특정한 열쇠가 필요한 상황에서 그 열쇠가 있는지 어떻게 판단할 것인가.

 

방법은 아주 다양하다. List, Set 같은 Collection에도 담을 수 있으며, Array도 활용할 수 있겠다. 하지만 비트로 표현하면 더욱 적은 메모리로 활용이 가능하다.

 

열쇠가 없다면 000000

a, d라는 열쇠를 갖고 있다면 001001

c, e, f라는 열쇠를 갖고 있다면 110100

모든 열쇠를 갖는다면 111111

 

위와 같이 간단하게 0과 1만으로 무엇이 있는지 확인할 수 있다.

---

> 십진수 -> 이진수 출력

    static void printBit(int x){

        for(int i=16; i>0; i--)
            System.out.print((x & (1 << i-1)) == (1 << i-1)? 1:0);

        System.out.println();
    }
    //x = 13일 때
    //0000000000001101

 

> 모든 Bit 0으로 Set

모든 Bit를 0으로 만들고자 할 때는 변수를 0으로 초기화 시킨다. 컴퓨터는 2의 보수 체계를 갖으므로 0으로 초기화하면 모든 비트가 0으로 된다.

    static int setAllZero(int x){
        return x = 0;
    }
    //0000000000000000

 

> 모든 Bit 1으로 Set

모든 Bit를 1로 만들고자 할 때는 변수를 -1로 초기화 시킨다. 컴퓨터는 2의 보수 체계를 갖으므로 -1로 초기화 하면 모든 비트가 1로 된다.

    static int setAllOne(int x){
        return x = -1;
    }
    //1111111111111111

 

> 특정 Bit 1로 만들기

i번째 원소를 1로 만들 때는 (1 << i)와 OR(|) 연산을 적용한다. (1 << i)는 i번째 비트만 1이고 나머지는 0이기 때문에 해당 원소에만 영향을 미친다.

        System.out.println("5번째 Bit를 1로 만들기");
        a = 13;
        a |= (1 << 5);
        printBit(a);
        //0000000000101101

 

> 특정 Bit 0으로 만들기

i번째 원소를 0으로 만들 때는 (1 << i)에 NOT(~) 연산을 적용하여 AND(&) 연산을 적용한다. ~(1 << i)는 i번 째 비트만 0이고 나머지는 전부 1이다.

        System.out.println("5번째 Bit를 0으로 만들기");
        a &= ~(1 << 5);
        printBit(a);
        //0000000000001101

 

> 특정 Bit를 Toggle 시키기

Toggle이란, 해당 비트가 0이면 1로, 1이면 0으로 만드는 것이다. (1 << i)와 XOR(^)연산을 적용한다.

        System.out.println("5번째 Bit를 Toggle 시키기 (0 -> 1, 1 -> 0)");
        a ^= (1 << 5);
        printBit(a);
        //0000000000101101

 

> 마지막 Bit 구하기

컴퓨터는 내부적으로 2의 보수 체계를 사용하므로 -a는 a에 대한 1의 보수에서 1을 더한 값과 동일하기 때문에 a와 -a를 AND연산 하면 가장 작은 비트인 마지막 비트를 구할 수 있다. 이 때 마지막 비트는 정수형으로 반환된다. 오른쪽에서 3번째 원소라면 2^(3-1) = 4가 된다.

        System.out.println("마지막 원소 구하기");
        System.out.println(a & -a);
        //1

 

> 마지막 Bit 0으로 만들기

마지막 Bit를 0으로 만들기 위해서는 a와 (a-1)을 AND 연산하면 된다. a-1은 a의 가장 마지막 비트를 0으로 바꾸고 그보다 작은 비트들을 모두 0으로 바꾸기 때문이다.

        System.out.println("마지막 원소 삭제하기");
        a &= (a-1);
        printBit(a);
        //0000000000101100

# Code </>

    static void printBit(int x){

        for(int i=16; i>0; i--)
            System.out.print((x & (1 << i-1)) == (1 << i-1)? 1:0);

        System.out.println();
    }
    static int setAllZero(int x){
        return x = 0;
    }
    static int setAllOne(int x){
        return x = -1;
    }

    public static void main(String[] args) throws IOException {

        int a = 13;

        System.out.println("13's Binary Digit");
        printBit(a);

        System.out.println("모든 비트를 0으로 set");
        printBit(setAllZero(a));

        System.out.println("모든 비트를 1로 set");
        printBit(setAllOne(a));

        a = 13;
        System.out.println("3번째 Bit는 무엇일까?");
        System.out.println((a & (1 << 3)) == (1 << 3)? 1:0);

        System.out.println("5번째 Bit를 1로 만들기");
        a = 13;
        a |= (1 << 5);
        printBit(a);

        System.out.println("5번째 Bit를 0으로 만들기");
        a &= ~(1 << 5);
        printBit(a);

        System.out.println("5번째 Bit를 Toggle 시키기 (0 -> 1, 1 -> 0)");
        a ^= (1 << 5);
        printBit(a);

        System.out.println("마지막 원소 구하기");
        System.out.println(a & -a);

        System.out.println("마지막 원소 삭제하기");
        a &= (a-1);
        printBit(a);
    }

# References

안경잡이 개발자님의 블로그

마이구미님의 블로그