비트 맵 법: 하나의 수가 40 억 개의 정수 에 있 는 지 판단 합 니까?

제목.
최근 에 한 문 제 를 보 았 습 니 다. 40 억 개의 중복 되 지 않 는 unsigned int 의 정 수 를 주 고 순 서 를 정 하지 않 은 다음 에 한 개의 수 를 주 었 습 니 다. 이 수가 그 40 억 개의 수 에 있 는 지 어떻게 신속하게 판단 합 니까?
 
해법
자 료 를 찾 아 보 니 이 문 제 는 텐 센트 의 면접 문제 로 현재 인터넷 에서 보편적으로 내 놓 은 답 은 두 가지 가 있다.
1. 주옥 같은 프로 그래 밍 방안
우 리 는 40 억 개의 숫자 중 하 나 를 32 비트 의 바 이 너 리 로 표시 하고 이 40 억 개의 숫자 를 하나의 파일 에 넣 기 시작 했다 고 가정 한다.
그리고 이 40 억 개의 수 를 두 가지 로 나눈다. 1. 최고 위 는 0 이다.2. 최고 위 는 1 이다.
그리고 이 두 가 지 를 각각 두 파일 에 기록 합 니 다. 그 중에서 한 파일 의 갯 수 는 < 20 억, 다른 하 나 는 > 20 억 (이것 은 절반 에 해당 합 니 다) 입 니 다.
찾 을 수의 가장 높 은 위치 와 비교 한 다음 해당 파일 에 들 어가 서 찾 습 니 다.
그 다음 에 이 파일 을 두 가지 로 나 누 었 습 니 다. 1. 차 의 최고 위 는 0 입 니 다.2. 차 최고 위 는 1 이다.
그리고 이 두 가 지 를 각각 두 파일 에 기록 합 니 다. 그 중에서 한 파일 의 개수 < = 10 억, 다른 하 나 는 > = 10 억 (이것 은 절반 에 해당 합 니 다).찾 을 수의 최고 위 치 를 비교 한 다음 해당 파일 에 들 어가 서 찾 습 니 다.
 .......
이런 식 으로 유추 하면 찾 을 수 있 고 시간 복잡 도 는 O (logn) 이다.
 
이 방안 은 본 고가 말 하고 자 하 는 중점 이 아니 라, 단지 사고방식 을 여기에 놓 아 모두 가 참고 하도록 제공 할 뿐이다.
 
2. 비트 맵
사고의 방향
우리 가 40 억 개의 숫자 를 메모리 에 직접 읽 어 처리 할 수 없 는 이 유 는 40 억 개의 unsigned int 의 정수 가 약 15G 메모 리 를 차지 하기 때 문 입 니 다. 정상 적 인 상황 에서 이렇게 큰 메모리 가 없 으 면 이렇게 할 수 없습니다.
이런 상황 은 하나의 정수 가 4 개의 바이트 (Byte) 를 차지 하기 때문에 이 문제 에서 우 리 는 사실 특정한 숫자 가 존재 하 는 지 에 만 관심 을 가진다. 이런 상황 에서 우 리 는 비트 맵 법 을 통 해 이 문 제 를 해결 할 수 있다.
비트 맵 사상: 40 억 개의 unsigned int 에 대해 의 정수, 각 숫자 는 1 개의 바 이 너 리 (1 개의 바 이 너 리 수 는 1Bit, 1Byte = 8Bit) 로 이 숫자 가 존재 하 는 지, 0 은 존재 하지 않 는 지, 1 은 존재 하 는 지 를 나타 낸다.낮은 자리 부터 세 기 를 시작 합 니 다:
첫 번 째 이 진 수 는 정수 0 이 존재 하 는 지 여 부 를 나타 낸다.
두 번 째 이 진 수 는 정수 1 이 존재 하 는 지 여 부 를 나타 낸다.
세 번 째 이 진 수 는 정수 2 가 존재 하 는 지 여 부 를 나타 낸다.
순서대로 유추 하 다.
제4 294967296 개의 이 진 수 는 정수 4294967295 의 존재 여 부 를 나타 내 는 데 쓰 인 다.
unsigned int 는 32 & 64 비트 컴 파일 러 의 범 위 는 0 ～ 4294967295 이 고 4294967296 개의 바 이 너 리 수 는 약 512 M 메모 리 를 차지 하 며 받 아들 일 수 있 는 범위 이다.
 
예시
제목: 우 리 는 3 개의 정 수 를 읽 었 다. 1, 2, 4. 정수 3 이 읽 혔 는 지 판단 해 야 한다.
해답 과정:
1) 40 억 개의 unsigned int 에 대해 의 정 수 는 4294967296 개의 바 이 너 리 수 를 정의 할 수 있 고 모든 초기 화 값 은 0 입 니 다.
2) 읽 기 정수 1: 두 번 째 바 이 너 리 할당 값 을 1 로 하여 정수 1 이 존재 한 다 는 것 을 나타 낸다. 이때 값 은 10 (높 은 자리 에 4294967294 개 0 이 있 는데 읽 기 편 하도록 쓰 지 않 으 면 다음 과 같다) 이다.
3) 읽 기 정수 2: 세 번 째 바 이 너 리 할당 값 을 1 로 하여 정수 2 가 존재 한 다 는 것 을 나타 낸다. 이때 값 은 110 이다.
4) 읽 기 정수 4: 다섯 번 째 바 이 너 리 할당 값 을 1 로 하여 정수 4 가 존재 한 다 는 것 을 나타 낸다. 이때 값 은: 10110 이다.
5) 정수 3 이 읽 혔 는 지 여 부 를 판단 한다. 첫 번 째 이 진 수 는 정수 0 이 존재 하 는 지 여 부 를 나타 내기 때문에 정수 3 은 네 번 째 이 진 수 를 통 해 표시 한다. 이때 의 값 은 10110 이 고 네 번 째 이 진 수 는 0 이기 때문에 정수 3 은 읽 힌 적 이 없다.
 
코드 구현
자바 에서 바 이 너 리 수 를 직접 조작 할 수 없 기 때문에 int 를 통 해 이 루어 질 수 있 습 니 다.1 개 이 진수 점용 1 Bit；1 개의 int 는 4 Byte, 즉 32 비트 를 차지한다.따라서 우 리 는 1 개의 int 를 사용 하여 32 개의 이 진 수 를 표시 할 수 있다.
그래서 우 리 는 다음 과 같은 생각 이 있다.
첫 번 째 int 는 정수 0 ~ 31 이 존재 하 는 지,
두 번 째 int 는 정수 32 ~ 63 이 존재 하 는 지,
세 번 째 int 는 정수 64 ~ 95 가 존재 하 는 지 여 부 를 유추 한다.
따라서 우 리 는 최종 적 으로 하나의 int 배열 을 사용 하여 4294967296 개의 바 이 너 리 수 를 표시 하고 배열 의 아래 표 시 를 통 해 몇 번 째 int 를 표시 할 수 있다.
코드 는 다음 과 같다.

package com.joonwhee.open.leetcode.temp;

/**
 *    
 *
 * @author joonwhee
 * @date 2019/1/22
 */
public class BitMap {
    /**
     *          ,
     *   unsigned int     4294967295,     length 4294967296
     */
    private long length;

    /**
     *    
     */
    private static int[] bitmapBucket;

    /**
     * int    32     ,
     * BIT_VALUE[0]   1       、
     * BIT_VALUE[1]   2       ，    
     *
     * BIT_VALUE[0] = 00000000 00000000 00000000 00000001
     * BIT_VALUE[1] = 00000000 00000000 00000000 00000010
     * BIT_VALUE[2] = 00000000 00000000 00000000 00000100
     * ...
     * BIT_VALUE[31] = 10000000 00000000 00000000 00000000
     */
    private static final int[] BIT_VALUE = {
            0x00000001, 0x00000002, 0x00000004, 0x00000008,
            0x00000010, 0x00000020, 0x00000040, 0x00000080,
            0x00000100, 0x00000200, 0x00000400, 0x00000800,
            0x00001000, 0x00002000, 0x00004000, 0x00008000,
            0x00010000, 0x00020000, 0x00040000, 0x00080000,
            0x00100000, 0x00200000, 0x00400000, 0x00800000,
            0x01000000, 0x02000000, 0x04000000, 0x08000000,
            0x10000000, 0x20000000, 0x40000000, 0x80000000};

    /**
     * length 1 - 32:   1  
     * length 33 - 64:   2  
     * ...
     *     
     *
     * @param length
     */
    public BitMap(long length) {
        this.length = length;
        //       ，       
        bitmapBucket = new int[(int) (length >> 5) + ((length & 31) > 0 ? 1 : 0)];
    }

    /**
     *   number         
     *
     * @param number       
     * @return true: number     , false: number      
     */
    public boolean getBit(long number) {
        if (number < 0 || number > length) {
            throw new IllegalArgumentException("    ");
        }
        //    number    
        int belowIndex = (int) (number >> 5);
        //    number      ,（     32      ,   0 - 31）
        int offset = (int) (number & 31);
        //       
        int currentValue = bitmapBucket[belowIndex];
        //    number    
        return ((currentValue & BIT_VALUE[offset])) == 0 ? false : true;
    }

    /**
     *  number          
     *
     * @param number       
     */
    public void setBit(long number) {
        //      
        if (number < 0 || number >= length) {
            throw new IllegalArgumentException("    ");
        }
        //    number    
        int belowIndex = (int) (number >> 5);
        //    number      ,（     32      ,   0 - 31）
        int offset = (int) (number & 31);
        //         
        int currentValue = bitmapBucket[belowIndex];
        //  number     
        bitmapBucket[belowIndex] = currentValue | BIT_VALUE[offset];
    }

    public static void main(String[] args) {
        BitMap bitMap = new BitMap(4294967296L);
        bitMap.setBit(4294967295L);
        System.out.println(bitMap.getBit(4294967295L));
        System.out.println(bitMap.getBit(4294967294L));
    }
}

사고방식 을 이해 한 후에 코드 는 비교적 간단 해 졌 다.
1) 구조 함수 가 전달 하 는 length 값 을 통 해 충분 한 int 배열 bitmapBucket 을 구축 하고 제목 의 unsigned int 의 정수 에 대해 length 는 4294967296 으로 충분 합 니 다.
2) 주어진 수 40 억 개 를 setBit 방법 으로 대응 하 는 위치의 이 진 수 를 1 (1 은 존재 함) 로 표시 한다.
3) getBit 로 방법 은 주어진 number 가 이전의 40 억 개 수 에 존재 하 는 지 여 부 를 판단 한다.
 
setBit 예: 예 를 들 어 우 리 는 정수 32 를 존재 로 표시 해 야 합 니 다.
1) 먼저 정수 32 가 있 는 비트 맵 통 아래 표 시 된 것 을 1 로 계산 하면 bitmapBucket [1] 이다.
2) 이어서 정수 32 를 계산한다 bitmapBucket 에서 [1] 통 의 아래 표 시 는 0 이다.
3) bitmapBucket [1] 현재 값 currentValue 를 가 져 옵 니 다.
4) 마지막 으로 우 리 는 bitmapBucket [1] 을 통 의 첫 번 째 바 이 너 리 수 를 1 로 표시 하고 이전에 표 시 된 바 이 너 리 수 에 영향 을 주지 않 기 때문에 currentValue 0000 0000 0000 0000 0001 혹은 연산 하면 된다.그리고 모든 이 진수 에 대해 우 리 는 BIT 를 통 해VALUE 는 이쪽 0000 0000 0000 0000 0000 0001, BIT 를 통 해VALUE [0] 가 표시 합 니 다.