[Java] Java로 Bit 조작하기

Java 비트 조작(Bit Manipulation) 마스터하기

비트 조작이란?

• 컴퓨터 프로그래밍에서 개별 비트 수준에서 데이터를 다루는 기술
• 메모리와 CPU 사용을 최적화하는 저수준 프로그래밍 기법
• 특정 알고리즘에서 성능을 극대화할 수 있는 핵심 기술

비트 조작의 장점

• 성능 향상: 비트 연산은 CPU에서 직접 처리되어 매우 빠름
• 메모리 효율성: 여러 불리언 값을 하나의 정수에 저장 가능
• 알고리즘 최적화: 특정 문제에서 시간 및 공간 복잡도 개선
• 하드웨어 제어: 저수준 하드웨어 제어에 필수적

기본 비트 연산자

연산자	이름	설명	예시
&	AND	두 비트가 모두 1일 때만 1 반환	5 & 3 = 1
\|	OR	두 비트 중 하나라도 1이면 1 반환	5 \| 3 = 7
^	XOR	두 비트가 서로 다를 때만 1 반환	5 ^ 3 = 6
~	NOT	비트 반전 (0→1, 1→0)	~5 = -6
<<	왼쪽 시프트	비트를 왼쪽으로 이동	5 << 1 = 10
>>	오른쪽 시프트	비트를 오른쪽으로 이동 (부호 유지)	5 >> 1 = 2
>>>	부호 없는 오른쪽 시프트	비트를 오른쪽으로 이동 (부호 무시)	5 >>> 1 = 2

비트 연산 예제 시각화

5 = 00000000 00000000 00000000 00000101 (2진수)
3 = 00000000 00000000 00000000 00000011 (2진수)

5 & 3 = 00000000 00000000 00000000 00000001 = 1
5 | 3 = 00000000 00000000 00000000 00000111 = 7
5 ^ 3 = 00000000 00000000 00000000 00000110 = 6
~5    = 11111111 11111111 11111111 11111010 = -6

유용한 비트 조작 기법

1. 특정 비트 확인

// n의 pos 위치 비트가 1인지 확인
boolean isBitSet(int n, int pos) {
    return (n & (1 << pos)) != 0;
}

2. 특정 비트 설정(1로 만들기)

// n의 pos 위치 비트를 1로 설정
int setBit(int n, int pos) {
    return n | (1 << pos);
}

3. 특정 비트 클리어(0으로 만들기)

// n의 pos 위치 비트를 0으로 설정
int clearBit(int n, int pos) {
    return n & ~(1 << pos);
}

4. 특정 비트 토글(반전)

// n의 pos 위치 비트를 반전
int toggleBit(int n, int pos) {
    return n ^ (1 << pos);
}

5. 최하위 비트 제거

// n의 최하위 1 비트를 제거
int clearLowestSetBit(int n) {
    return n & (n - 1);
}

6. 최하위 비트 추출

// n의 최하위 1 비트만 남김
int getLowestSetBit(int n) {
    return n & -n;  // 또는 n & (~n + 1)
}

Integer 클래스의 비트 관련 메소드

Java의 Integer 클래스는 비트 조작을 위한 다양한 유틸리티 메소드를 제공합니다:

메소드	설명	예시
Integer.bitCount(n)	1 비트의 개수 반환	Integer.bitCount(7) = 3
Integer.highestOneBit(n)	최상위 1 비트만 남김	Integer.highestOneBit(10) = 8
Integer.lowestOneBit(n)	최하위 1 비트만 남김	Integer.lowestOneBit(10) = 2
Integer.numberOfLeadingZeros(n)	선행 0의 개수	Integer.numberOfLeadingZeros(8) = 28
Integer.numberOfTrailingZeros(n)	후행 0의 개수	Integer.numberOfTrailingZeros(8) = 3
Integer.rotateLeft(n, d)	왼쪽으로 d비트 회전	Integer.rotateLeft(8, 1) = 16
Integer.rotateRight(n, d)	오른쪽으로 d비트 회전	Integer.rotateRight(8, 1) = 4
Integer.reverse(n)	비트 순서 뒤집기	Integer.reverse(43) = 2752782336
Integer.reverseBytes(n)	바이트 순서 뒤집기	Integer.reverseBytes(0x12345678) = 0x78563412

비트 조작 활용 예제

1. 짝수/홀수 확인

boolean isEven(int n) {
    return (n & 1) == 0;  // 최하위 비트가 0이면 짝수
}

2. 2의 거듭제곱 확인

boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

3. 절댓값 계산 (분기 없이)

int absoluteValue(int n) {
    return (n ^ (n >> 31)) - (n >> 31);
    // 또는 더 간단하게: (n < 0) ? -n : n
}

4. 두 수 중 최대/최소값 (분기 없이)

int max(int a, int b) {
    return b ^ ((a ^ b) & -(a > b ? 1 : 0));
}

int min(int a, int b) {
    return a ^ ((a ^ b) & -(a > b ? 1 : 0));
}

5. 비트 마스크를 이용한 집합 연산

class BitSet {
    private int set = 0;
    
    // 요소 추가
    void add(int element) {
        set |= (1 << element);
    }
    
    // 요소 제거
    void remove(int element) {
        set &= ~(1 << element);
    }
    
    // 요소 포함 여부 확인
    boolean contains(int element) {
        return (set & (1 << element)) != 0;
    }
    
    // 합집합
    BitSet union(BitSet other) {
        BitSet result = new BitSet();
        result.set = this.set | other.set;
        return result;
    }
    
    // 교집합
    BitSet intersection(BitSet other) {
        BitSet result = new BitSet();
        result.set = this.set & other.set;
        return result;
    }
}

실전 문제: 비트 카운팅 최적화

0부터 n까지의 각 정수에 대해 이진 표현에서 1의 개수를 계산하는 코드

public class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            res[i] = Integer.bitCount(i);
        }
        return res;
    }
}

위 코드는 Integer.bitCount()를 사용하여 간단하게 구현했지만, 비트 조작 기법을 활용하면 직접 구현할 수도 있습니다:

public class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            // i & (i-1)은 최하위 1 비트를 제거한 결과
            // 따라서 res[i]는 res[i & (i-1)] + 1과 같음
            res[i] = res[i & (i-1)] + 1;
        }
        return res;
    }
}

이 최적화된 방법은 동적 프로그래밍과 비트 조작을 결합하여 O(n) 시간 복잡도로 문제를 해결합니다.

비트 조작의 응용 분야

• 암호화: XOR 연산을 이용한 간단한 암호화
• 그래픽 처리: 이미지 처리 및 컴퓨터 그래픽스
• 네트워크 프로그래밍: IP 주소 및 서브넷 마스크 처리
• 게임 개발: 게임 상태 및 플래그 관리
• 임베디드 시스템: 제한된 리소스에서의 최적화
• 알고리즘 최적화: 특히 동적 프로그래밍 문제에서 상태 표현