[알고리즘][비트연산] 3. 비트 뒤집기

문제: 임의의 64비트 숫자의 비트열을 역순으로 만들어 리턴하라.

 

가장 단순한 방법은 2. 비트 스왑에서 사용한 해법을 모든 비트에 적용하는 것이다. 이 방법을 사용하면 입력의 크기 n에 대해 O(n)의 시간이 소요된다.

public static long flip(long x) {
    int i = 63;
    for (int j = 0; j <= 31; j++) {
        if (((x >>> i) & 1) != ((x >>> j) & 1)) {
            x ^= (1L << i);
            x ^= (1L << j);
        }
        i--;
    }
    return x;
}

 

더 빠른 방법은 lookup table을 사용하는 것이다. 일종의 캐시 기능을 하는 테이블을 통해 공간을 더 사용하면서 시간복잡도를 O(n/캐시의 크기)로 줄일 수 있다.

 

64비트 입력의 경우 이를 16비트씩 4등분하여 {0x0001, 0x0002, 0x0003, 0x0004}처럼 나누고, 역순으로 만들기 위해 {0x0004의 역순, 0x0003의 역순, 0x0002의 역순, 0x0001의 역순}처럼 배치할 수 있다. 각 역순 비트열은 아래처럼 미리 계산해 둔 테이블을 참조함으로써 얻을 수 있다.

int[] table = {
    0b0000000000000000_0000000000000000,     // table[0]
    0b0000000000000000_1000000000000000,     // table[1]
    0b0000000000000000_0100000000000000,     // table[2]
    // 중략
    0b0000000000000000_1011111111111111,     // table[65533] 
    0b0000000000000000_0111111111111111,     // table[65534] 
    0b0000000000000000_1111111111111111,     // table[65535] 
}

이 방법을 응용하면, 64비트 입력에 대해 아래와 같은 코드를 작성할 수 있다.

public static long fastFlip(long x) {
    return (long)table[(int)(x & 0xFFFF)       ] << 48 |
           (long)table[(int)(x >>> 16 & 0xFFFF)] << 32 |
           (long)table[(int)(x >>> 32 & 0xFFFF)] << 16 |
           (long)table[(int)(x >>> 48 & 0xFFFF)] ;
}

연산에 걸리는 시간을 비교해 보면, long형 정수 100억 ~ 200억을 입력했을 때, 룩업 테이블 방법은 14.62초가 소요되었고, 비트 스왑 방법은 10분 정도 기다리다가 안끝나길래 종료시켰습니다.

 

연산 시간을 측정할 때는 아래처럼 System.currentTimeMillis();를 사용했다.

long startTime = System.currentTimeMillis();
// 연산 수행
long endTime = System.currentTimeMillis();
System.out.println(endTime - startTime);