[알고리즘][비트연산] 2. 비트 스왑

문제: 임의의 64비트 수 x의 i번째 비트와 j번째 비트를 교환하라. (0 ≤ i, j ≤ 63)

 

일반적인 배열 내에서 특정 위치의 값들을 스왑하기 위해서는 그 값을 저장할 변수가 필요하다. 그러나 비트는 어차피 0과 1밖에 없기 때문에, 두 위치의 비트가 다를 때만 해당 위치들의 비트를 반전시켜주면 문제를 상수 시간 내에 해결할 수 있다.

 

public static long swap(long x, int i, int j) {
	if (((x >>> i) & 1) != ((x >>> j) & 1)) {
    	x ^= 1L << i;
        x ^= 1L << j;
    }
    return x;
}