비트마스킹 가이드 : 기본 개념과 실전 예제

비트마스킹이란

 

이진수와 비트 연산을 활용하여 여러 상태를 하나의 정수로 관리하는 방법으로 메모리 효율성과 연산 속도를 높임

 

- 비트 연산자

비트 연산은 상수 시간(O(1))에 수행

 

• AND (&): 두 비트가 모두 1일 때만 1을 반환
• OR (|): 두 비트 중 하나라도 1이면 1을 반환
• XOR (^): 두 비트가 다를 때만 1을 반환
• NOT (~): 비트값을 반전 (0은 1로, 1은 0으로)
• SHIFT LEFT (<<): 비트를 왼쪽으로 이동 (2의 n 제곱을 곱하는 효과)
• SHIFT RIGHT (>>): 비트를 오른쪽으로 이동 (2의 n 제곱을 나누는 효과)

 

- 특정 비트 조작

 

• 특정 비트 켜기: x |= (1 << i) - x의 i번째 비트를 1로 설정
• 특정 비트 끄기: x &= ~(1 << i) - x의 i번째 비트를 0으로 설정
• 특정 비트 반전: x ^= (1 << i) - x의 i번째 비트를 반전
• 특정 비트 값 확인 : x & (1 << i) x의 i번째 비트를 확인

초기 비트가 10을 이진수로 나타낸 1010일 때

첫번째 비트를 키기 위해서는

1010

0001(1 << 1)

두 비트의 OR 연산을 하면 둘 중 하나라도 1이면 1을 반환하므로 1011과 같이 첫번째 비트를 킬 수 있습니다

 

마찬가지로 두번째 비트를 끄기 위해서는

1011

1101(~(1<<2))

두 비트의 AND 연산을 하면 두 비트가 모두 1일때만 1을 반환하므로 1001과 같이 두번째 비트를 끌 수 있습니다

 

또한 세번째 비트의 값을 변경하기 위해서는

1001

0100(1<<3)

두 비트의 XOR 연산을 하면 두 비트가 다를 때만 1을 반환하므로(바꾸고 싶은 위치에 1을 넣고 XOR 연산을 하므로 바꾸고 싶은 위치가 1이면 같아서 0, 0이면 달라서 1로 반전됨) 1101과 같이 세번째 비트의 값을 반전 시킬 수 있습니다

 

네번째 비트의 값을 확인하기 위해서는

1101

1000(1<<4)

두 비트의 AND 연산을 하면 두 비트가 모두 1일때만 1을 반환하므로 반환값이 해당 위치의 값과 동일해집니다

비트마스킹 예제

 

- 정수값 활용

 

1. 이진수로 나타냈을 때 1의 개수 세기

 

    public static void main(String[] args) {
        int num = 13; // 1101
        int count = 0;
        while (num != 0) {
            // 첫번째 자리가 1이면 1, 아니면 0 더해주기
            count += num & 1;
            // 숫자를 2로 나누기(1101 -> 0110)
            num >>= 1;
        }
        System.out.println("1의 개수: " + count);
        //Integer의 메서드로 쉽게 구할 수도 있음
        System.out.println("1의 개수: " + Integer.bitCount(num));
    }

 

 

2. 2의 거듭제곱 확인

 

    public static void main(String[] args) {
        int n1 = 5; // 0101
        int n2 = 8; // 1000

        System.out.println("n1은 2의 거듭제곱? : " + isPowerOfTwo(n1));
        System.out.println("n2는 2의 거듭제곱? : " + isPowerOfTwo(n2));
    }

/* 2의 거듭제곱이려면 자릿수 중 단 한곳만 1
   이 상황에서 n - 1을 하면 1이었던 자리의 아랫 자리는 전부 1(1000 -> 0111)
   즉, n과 n-1을 AND 연산했을 때 0이 나오면 2의 거듭제곱 */
    private static boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n-1)) == 0;
    }

 

3. 두 수 교환하기

 

이 코드를 이해하기 전에 XOR 연산의 특성을 알아봅시다

 

• x ^ x = 0 : 동일한 값을 XOR하면 0(모두 같은 값이므로 0)
• x ^ 0 = x : 어떤 값과 0을 XOR하면 원래 값(1은 1, 0은 0 그대로 반환되므로)
• x ^ y ^ y = x : XOR 연산은 교환법칙과 결합법칙이 성립, x ^ y ^ y는 x ^ (y ^ y)와 같으며, 이는 x ^ 0이므로 결과는 x

 

    public static void main(String[] args) {
        int n1 = 5; //0101
        int n2 = 7; //0111
        n1 ^= n2; // n1 = 0010
        n2 ^= n1; // n2 = 0101
        n1 ^= n2; // n1 = 0111

        System.out.println("a : " + n1 + ", " + "b : " + n2);
    }

 

n1 ^= n2를 하면 n1 = n1^n2

n2 ^= n1을 하면 n2 = n1^n2^n2 = n1^0 = n1

n1 ^= n2를 하면 n1 = n1^n2^n1 = 0^n2 = n2 

따라서 두 값을 교환할 수 있습니다

 

- 상태 저장 활용

 

1. 상태 저장

 

    public static void main(String[] args) {
        int state = 0; // 상태를 저장할 변수
        // 각 상태는 2의 거듭제곱꼴로 정의
        final int VISITED = 1;
        final int HAS_ITEM = 2;
        final int IS_LOCKED = 4;

// 상태 설정 : |= 연산으로 해당 상태 비트 켜기
        state |= VISITED | HAS_ITEM;

// 상태 확인 : &연산으로 해당 상태 비트가 켜져있으면 1, 꺼져있으면 0 반환
        if ((state & VISITED) == 0) {
            System.out.println("방문하지 않음");
        } else {
            System.out.println("방문했음");
        }
        if ((state & HAS_ITEM) == 0) {
            System.out.println("아이템을 가지고 있지 않음");
        } else {
            System.out.println("아이템을 가지고 있음");
        }
        if ((state & IS_LOCKED) == 0) {
            System.out.println("잠겨있지 않음");
        } else {
            System.out.println("잠겨 있음");
        }

 

 

2. 부분집합 구하기

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};

        // 부분집합의 개수는 2^n(1 << n)이므로 1 << n 만큼 반복
        for (int i = 0; i < (1 << arr.length); i++) {
            System.out.print("부분집합: ");
            // 각 원소 검사(0번 인덱스 ~ 3번 인덱스)
            for (int j = 0; j < arr.length; j++) {
                /*
                i는 0~15이고 각 자릿수가 1이면 해당 인덱스 수 포함, 0이면 포함하지 않음
                (1<<j) j번재 비트만 1인 이진수로 만듬
                i & (i<<j)로 해당 인덱스가 포함인지 확인 (1이면 포함, 0이면 포함하지 않음)
                 */
                if ((i & (1 << j)) != 0) {
                    System.out.print(arr[j] + " ");
                }
            }
            System.out.println();
        }
    }

 

3. 2차원 배열 상태 저장

 

3*3모양의 도장이 있고 각 도장은 90도 단위로 회전한 경우에도 모두 같은 도장이라 할 때 주어진 도장 중 서로 다른 모양의 도장 종류는 몇개인지 확인하는 코드를 짠다고 생각해봅시다

 

    private static Map<Integer, Integer> stampMap = new HashMap<>();
    private static int stampCount = 0;

    public static void main(String[] args) {
        // 예시 도장들
        int[][] stamp1 = {
                {1,1,1},
                {1,0,0},
                {1,0,0}};
        int[][] stamp2 = {
                {1,1,1},
                {0,0,1},
                {0,0,1}};
        int[][] stamp3 = {
                {1,0,0},
                {1,0,0},
                {1,1,1}};
        int[][] stamp4 = {
                {0,0,1},
                {0,0,1},
                {1,1,1}};
        int[][] stamp5 = {
                {1,0,0},
                {0,0,1},
                {0,1,0}};
        int[][] stamp6 = {
                {0,0,1},
                {1,0,0},
                {0,1,0}};

        checkAndAddStamp(stamp1);
        checkAndAddStamp(stamp2);
        checkAndAddStamp(stamp3);
        checkAndAddStamp(stamp4);
        checkAndAddStamp(stamp5);
        checkAndAddStamp(stamp6);

        System.out.println("총 유니크한 도장 개수: " + stampCount);
    }

    private static void checkAndAddStamp(int[][] stamp) {
        int bitMask = convertToBitMask(stamp);

        // 이미 존재하는 도장이면 메서드 종료
        if (stampMap.containsKey(bitMask)) {
            System.out.println("이미 존재하는 도장입니다. 번호: " + stampMap.get(bitMask));
            return;
        }
         // 존재하지 않는 도장이면 90도씩 돌리면서 추가
        for (int i = 0; i < 4; i++) {
            stampMap.put(bitMask, stampCount+1);
            bitMask = rotateBitMask(bitMask);
        }
        stampCount++;
        System.out.println("새로운 도장이 추가되었습니다. 번호: " + stampCount);
    }

    private static int convertToBitMask(int[][] stamp) {
        int mask = 0;
        // 도장의 각 칸을 확인하면서
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                // 1인 경우 해당 비트 부분을 켜줍니다
                if (stamp[i][j] == 1) {
                    mask |= (1 << (i * 3 + j));
                }
            }
        }
        return mask;
    }

    private static int rotateBitMask(int mask) {
        int rotated = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                // 현재 위치가 1 즉, 켜져있는 비트인지 확인
                if ((mask & (1 << (i * 3 + j))) != 0) {
                    // 켜져있다면 90도 회전 즉, (j, n - i)위치의 비트를 켜줌
                    rotated |= (1 << (j * 3 + (2 - i)));
                }
            }
        }
        return rotated;
    }