예제로 배우는 알고리즘 - 비트 마스킹

이진수 더하기

 

예제 - LeetCode 67. Add Binary

https://leetcode.com/problems/add-binary/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 이해

•  문자열로 주어진 두 이진수를 더한 값을 이진 문자열로 나타내기

 

2. 요구사항 분석

• 입력
  • 1<= a,length, b.length <= 10,000
  • 각 문자열의 요소는 0 또는 1
  • 0을 제외하고는 0으로 시작하지 않음
• 출력
  • 이진 문자열

 

3. 해결 아이디어

• 가장 낮은 자리부터 더해가기
• 더한 값을 2로 나누어 몫은 올림값에 나머지는 결과에 저장하기
• 낮은 자리부터 더했으므로 뒤집은 값을 반환

 

4. 시간 복잡도 및 공간 복잡도 확인

 

• 시간 복잡도
  • 자릿수를 하나씩 확인하므로 O(n)
• 공간 복잡도
  • 결과를 저장할 StringBuilder가 필요하므로 O(n)

 

5. 구현

class Solution {
    public static String addBinary(String a, String b) {
        // 1. 결과를 저장할 StringBuilder 할당
        StringBuilder sb = new StringBuilder();
        
        // 2. 계산할 자리와 올림값 할당
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;

        // 3. 이진수의 합 계산
        // 3-1) 계산할 자리가 남거나 올림값이 남으면 반복
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry; // 합을 저장할 변수
            // 3-2) 문자를 정수로 변경
            if (i >= 0) sum += a.charAt(i--) - '0';
            if (j >= 0) sum += b.charAt(j--) - '0';
            
            // 3-3) 자리값과 올림값 저장
            sb.append(sum % 2);
            carry = sum / 2;
        }

        // 4. 결과 반환, 마지막 자리부터 결과에 더했으므로 뒤집어서 반환해야 함에 주의
        return sb.reverse().toString();
    }
}

 

이진수 뒤집기

 

예제 - LeetCode 190. Reverse Bits

https://leetcode.com/problems/reverse-bits/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 이해

• 32비트 정수의 비트를 거꾸로 뒤집어 반환

 

2. 요구사항 분석

• 입력
  • 32비트의 이진수로 나타낸 정수
• 출력
  • 비트를 뒤집은 정수의 십진수 형태

 

3. 해결 아이디어

• 함수가 반복 호출되는 경우를 고려하여 8비트로 나타낸 모든 정수의 뒤집은 값을 캐싱

• 비트 뒤집기
  
  • 1) 결과값의 자리값 하나 올리기(<< 연산)
  • 2) 입력값의 마지막 자리 확인 (&1 연산)
  • 3) 결과값의 마지막에 2)에서 확인한 값 더해주기(| 연산)
  • 4) 입력값의 다음 자리로 이동(>>> 연산)

 

4. 시간 복잡도 및 공간 복잡도 확인

 

• 시간 복잡도
  • 256개(상수)의 8비트 연산을 하므로 O(1)
• 공간 복잡도
  • 256개(상수)의 LOOKUP 배열이 필요하므로 O(1)

 

5. 구현

public class Solution {
    private static final int[] LOOKUP = new int[256];
        // 1. 8비트의 모든 이진수를 뒤집은 값을 미리 저장
        static {
            for (int i = 0; i < 256; i++) {
                LOOKUP[i] = reverseByte(i);
            }
        }

        // 2. 8비트 반전하기
        private static int reverseByte(int b) {
            int rev = 0;
            for (int i = 0; i < 8; i++) {
                rev <<= 1;    // 2-1) rev를 왼쪽으로 1비트 이동
                rev |= (b & 1); // 2-2) b의 마지막 비트를 rev에 추가
                b >>>= 1;       // 2-3) b를 오른쪽으로 1비트 이동
            }
            return rev;
        }

    public static int reverseBits(int n) {
        // 3. 32비트의 값을 8비트씩 나누 값 구하기
        // 3-1) & 0xFF를 이용하여 1인 부분 확인
        // 3-2) >>> 8을 통해 다음 8비트로 변경하고 남은 빈자리는 0으로 할당
        // * 0xff : 16진수로 나타낸 255(1111 1111)
        int b1 = n & 0xFF;
        int b2 = (n >>> 8) & 0xFF;
        int b3 = (n >>> 16) & 0xFF;
        int b4 = (n >>> 24) & 0xFF;

        // 4. 8비트씩 나눈 값의 뒤집은 값을 LOOKUP 배열에서 확인 후 합쳐주기(역순임에 주의)
        return (LOOKUP[b1] << 24)
                | (LOOKUP[b2] << 16)
                | (LOOKUP[b3] << 8)
                | (LOOKUP[b4]);
    }
}

 

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

 

예제 - LeetCode 191. Number of 1 Bits

https://leetcode.com/problems/number-of-1-bits/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 이해

• 정수를 이진수로 나타냈을 때 1의 개수 세기

 

2. 요구사항 분석

• 입력
  • n : int의 양의 범위
• 출력
  • 1의 개수(정수)

 

3. 해결 아이디어

• Brian Kernighan’s Algorithm
  
  • n & (n - 1)을 반복해서 n이 0이 될때까지의 반복 횟수
  • 예시 : 12(1100)
  • 1100 - 1 = 1011 => 제일 오른쪽의 1이 0으로 바뀌고 그 아래는 기존 수의 값과 반대가 됨
  • n & (n - 1) 연산 시 제일 오른쪽 1 위치부터 그 이후가 모두 0으로 바뀜
• 함수가 반복 호출되는 경우를 고려하여 8비트로 나타낸 모든 정수의 1의 갯수를 캐싱
  • 마지막 자리만 1인지 확인(&1 연산)
  • 마지막 자리를 제외한 1의 갯수는 이미 구한 값을 활용

 

4. 시간 복잡도 및 공간 복잡도 확인

 

• 시간 복잡도
  • Brian Kernighan’s Algorithm : O(logn)에 근접
  • 캐싱 : 256번(상수) 계산하므로 O(1)

• 공간 복잡도
  • Brian Kernighan’s Algorithm : 정적 변수만 사용하므로 O(1)
  • 캐싱 : 25 6개(상수)의 LOOKUP 배열이 필요하므로 O(1)

시간 복잡도에 이점이 있는 캐싱 방법을 선택

 

5. 구현

class Solution {
    private static final int[] LOOKUP = new int[256]; // 1의 개수를 저장할 배열

    // 1. 8비트의 모든 정수 1의 개수 캐싱
    static {
        // 마지막 자리만 확인, 나머지 자리는 기존에 구한 값 활용
        for (int i = 1; i < 256; i++) {
            LOOKUP[i] = (i & 1) + LOOKUP[i >> 1];
        }
    }

    // 2. 32비트의 정수 1의 개수 구하기
    // 2-1) >>> 연산으로 자리를 이동하며 & 0xff 연산으로 8비트씩 나누기
    // 2-2) LOOKUP 배열을 통해 1의 개수 합하기
    public int hammingWeight(int n) {
        return LOOKUP[n & 0xff] +
               LOOKUP[(n >>> 8) & 0xff] +
               LOOKUP[(n >>> 16) & 0xff] +
               LOOKUP[(n >>> 24) & 0xff];
    }
}

 

XOR 연산 활용

 

예제 - LeetCode 136. Single Number

https://leetcode.com/problems/single-number/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 이해

• 배열에서 한 번만 등장하는 요소 찾기(나머지는 두 번 등장)

 

2. 요구사항 분석

• 입력
  • 1 <= nums.length <= 30,000
  • -30,000 <= nums[i] <= 30,000
• 출력
  • 한번만 등장하는 수(정수)

 

3. 해결 아이디어

 

• XOR 연산 특징
  • a ^ a = 0
  • a ^ 0 = a
  • XOR은 교환/결합 법칙이 성립
• 모든 수를 XOR 연산 하면 짝수번 중복된 수는 사라짐을 활용

 

4. 시간 복잡도 및 공간 복잡도 확인

 

• 시간 복잡도
  • 배열을 한번 순회하면서 XOR 연산을 실행하므로 O(n)

• 공간 복잡도
  • 고정된 개수의 변수만 사용하므로 O(1)

 

5. 구현

class Solution {
    public int singleNumber(int[] nums) {
        // 1. 결과를 저장할 변수 할당
        int result = 0;

        // 2. 모든 수를 결과에 XOR 연산, 짝수번 반복되는 수는 사라짐
        for (int num : nums) {
            result ^= num;
        }

        return result;
    }
}

 

비트마스킹을 활용한 요소 갯수 확인

 

예제 - LeetCode 137. Single Number2

https://leetcode.com/problems/single-number-ii/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 이해

• 배열에서 한 번만 등장하는 요소 찾기(나머지는  번 등장)

 

2. 요구사항 분석

• 입력
  • 1 <= nums.length <= 30,000
  • nums[i]는 int 범위
• 출력
  • 한번만 등장하는 수(정수)

 

3. 해결 아이디어

 

• 모든 숫자들을 확인하며 비트마다 1이 몇번 들어가는지 확인
• 1이 들어간 수가 3의 배수가 아니라면 1을 표시(세 번이 아닌 경우에도 활용 가능)
  • ex) 3, 2, 3, 3라면 (2는 0010, 3은 0011) 세번째 비트에는 1이 4번,  네번째 비트에는 1이 3번 등장하므로 세번째비트에만 1을 표시하면 0010으로 한번만 등장하는 2를 찾을 수 있음
• 모든 비트를 확인하면 그 수가 한 번 등장하는 요소

 

4. 시간 복잡도 및 공간 복잡도 확인

 

• 시간 복잡도
  • 32비트 각각마다 n개의 수를 확인하므로 O(n)

• 공간 복잡도
  • 고정된 개수의 변수만 사용하므로 O(1)

 

5. 구현

class Solution {
    public int singleNumber(int[] nums) {
        // 1. 결과를 저장할 변수 할당
        int result = 0;

        // 2. 정수는 32비트니까, 각 비트 위치마다 주어진 숫자에서 1이 몇번 등장했는지 확인 후 3으로 나눠서 확인
        for (int i = 0; i < 32; i++) {
            int sum = 0; // i번째 비트의 개수
            int mask = 1 << i;  // i번째 비트를 확인하기 위한 마스크

            // 2-1) 모든 수의 i번째 비트가 1이면 갯수에 더하기
            for (int num : nums) {
                // 수와 mask의 & 연산 결과 0이면 해당 위치는 0
                if ((num & mask) != 0) {
                    sum++;
                }
            }

            // 2-2) 1의 개수가 3으로 나눠 떨어지지 않으면, 그 자리에 1이 있음
            if (sum % 3 != 0) {
                result |= mask;  // | 연산과 마스크를 활용하여 1표시
            }
        }

        return result;
    }
}

 

연속된 수의 & 연산 결과(공통 접두사)

 

예제 - LeetCode 201. Bitwise AND of Numbers Range

https://leetcode.com/problems/bitwise-and-of-numbers-range/description/?envType=study-plan-v2&envId=top-interview-150

 

 

1. 문제 이해

• 일정 범위의 수를 & 연산한 결과 구하기

 

2. 요구사항 분석

• 입력
  • 0 <= left <= right <= int의 양수 범위
• 출력
  • left에서 right 사이의 모든 수를 & 연산한 결과(정수)

 

3. 해결 아이디어

 

•  & 연산 중 어느 순간 하나라도 해당 비트가 0이면 결과에서 그 비트는 0이 됨
• left와 right의 공통 접두사만 결과에 유지가 됨
• >> 연산을 하며 공통 접두사 구하고 << 연산으로 나머지 비트를 0으로 만들기

 

4. 시간 복잡도 및 공간 복잡도 확인

 

• 시간 복잡도
  •  left와 right를 2씩 나누면서 확인하므로 O(logn)

• 공간 복잡도
  • 고정된 개수의 변수만 사용하므로 O(1)

 

5. 구현

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        // 1. 나중에 0으로 채울 비트 수 할당
        int shift = 0;
        
        // 2. 공통 접두사가 나올 때까지 오른쪽으로 시프트하며 확인, 같아지는 순간 반복문 중단
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        
        // 3. 공통 접두사 왼쪽으로 쉬프트 하면서 나머지 비트 0으로 채우기
        return left << shift;
    }
}