비트 연산 — AND 하나로 짝홀수 판별부터 권한 체크까지
컴퓨터는 결국 0과 1로 모든 것을 처리합니다. 그렇다면 0과 1을 직접 다루는 연산은 얼마나 강력할까요?
개념 정의
비트 연산(Bitwise Operation)은 정수를 이진수로 표현했을 때, 각 비트 단위로 수행하는 연산 입니다. CPU가 가장 빠르게 처리할 수 있는 연산이기도 합니다.
기본 비트 연산자
AND (&)
두 비트가 모두 1일 때만 1을 반환합니다.
// 짝홀수 판별: 마지막 비트가 0이면 짝수
int n = 7; // 0111
System.out.println(n & 1); // 1 → 홀수
int m = 6; // 0110
System.out.println(m & 1); // 0 → 짝수
OR (|)
두 비트 중 하나라도 1이면 1을 반환합니다.
// 플래그 설정(켜기)
int flags = 0b0010; // READ 권한만 있음
int WRITE = 0b0100;
flags = flags | WRITE; // 0110 → READ + WRITE
XOR (^)
두 비트가 다를 때 1을 반환합니다.
// 같은 값끼리 XOR하면 0
int a = 5;
System.out.println(a ^ a); // 0
// 배열에서 하나만 존재하는 원소 찾기
int[] arr = {2, 3, 2, 4, 3};
int result = 0;
for (int num : arr) {
result ^= num; // 짝을 이루는 수는 상쇄됨
}
System.out.println(result); // 4
NOT (~)
모든 비트를 반전시킵니다.
int n = 5; // 00000101
System.out.println(~n); // 11111010 → -6 (2의 보수)
SHIFT (<<, >>, >>>)
비트를 왼쪽 또는 오른쪽으로 이동시킵니다.
// 왼쪽 시프트: 2를 곱하는 효과
System.out.println(1 << 3); // 8 (1 → 1000)
System.out.println(5 << 1); // 10 (101 → 1010)
// 오른쪽 시프트: 2로 나누는 효과
System.out.println(8 >> 2); // 2 (1000 → 10)
// >>> : 부호 비트 무시하고 시프트 (논리적 시프트)
System.out.println(-1 >>> 1); // 2147483647 (Integer.MAX_VALUE)
왜 비트 연산이 필요한가
- **성능 **: CPU에서 가장 빠른 연산입니다. 곱셈/나눗셈 대신 시프트를 쓰면 빠릅니다.
- ** 메모리 절약 **: boolean 배열 대신 비트 하나로 상태를 표현할 수 있습니다.
- ** 플래그 패턴 **: 여러 개의 on/off 상태를 하나의 정수로 관리합니다.
플래그 패턴(비트마스크)
여러 권한이나 옵션을 하나의 정수로 관리하는 패턴입니다.
public class Permission {
static final int READ = 1 << 0; // 0001 = 1
static final int WRITE = 1 << 1; // 0010 = 2
static final int EXECUTE = 1 << 2; // 0100 = 4
static final int DELETE = 1 << 3; // 1000 = 8
// 권한 부여
static int grant(int current, int permission) {
return current | permission;
}
// 권한 제거
static int revoke(int current, int permission) {
return current & ~permission;
}
// 권한 확인
static boolean hasPermission(int current, int permission) {
return (current & permission) == permission;
}
// 권한 토글
static int toggle(int current, int permission) {
return current ^ permission;
}
}
// 사용 예시
int userPerm = 0;
userPerm = Permission.grant(userPerm, Permission.READ | Permission.WRITE);
System.out.println(Permission.hasPermission(userPerm, Permission.READ)); // true
System.out.println(Permission.hasPermission(userPerm, Permission.DELETE)); // false
userPerm = Permission.revoke(userPerm, Permission.WRITE);
System.out.println(Permission.hasPermission(userPerm, Permission.WRITE)); // false
리눅스 파일 권한 chmod 755도 이 원리입니다. 7 = 111(2) → rwx, 5 = 101(2) → r-x.
Java EnumSet — 비트마스크의 우아한 래퍼
Java의 EnumSet은 내부적으로 비트 벡터를 사용합니다. enum 상수가 64개 이하이면 long 하나로 관리합니다.
public enum Role {
READ, WRITE, EXECUTE, DELETE, ADMIN
}
// EnumSet 사용
EnumSet<Role> roles = EnumSet.of(Role.READ, Role.WRITE);
roles.add(Role.EXECUTE);
// 확인
System.out.println(roles.contains(Role.READ)); // true
System.out.println(roles.contains(Role.ADMIN)); // false
// 전체 권한
EnumSet<Role> allRoles = EnumSet.allOf(Role.class);
// 특정 권한 제외한 나머지
EnumSet<Role> complement = EnumSet.complementOf(roles);
HashSet보다 훨씬 빠르고 메모리도 적게 사용합니다. enum 기반 집합이 필요하면 항상 EnumSet을 사용하세요.
자주 쓰이는 비트 트릭
특정 비트 확인
// i번째 비트가 켜져 있는지 확인
boolean isSet = (n & (1 << i)) != 0;
최하위 켜진 비트(Lowest Set Bit)
int lowestBit = n & (-n);
// 예: n = 12 (1100) → lowestBit = 4 (0100)
비트 개수 세기
// Java 내장
int count = Integer.bitCount(n);
// 직접 구현 (Brian Kernighan 알고리즘)
int count = 0;
while (n != 0) {
n &= (n - 1); // 최하위 켜진 비트를 끔
count++;
}
2의 거듭제곱 판별
// n이 2의 거듭제곱이면 비트가 딱 1개만 켜져 있음
boolean isPowerOfTwo = (n > 0) && (n & (n - 1)) == 0;
비트마스크 DP
비트마스크는 DP에서 ** 집합의 상태 **를 표현할 때 사용됩니다. 대표적으로 외판원 문제(TSP)가 있습니다.
// 방문한 도시 집합을 비트마스크로 표현
// visited = 0b1011 → 0번, 1번, 3번 도시를 방문한 상태
int[][] dp = new int[1 << n][n]; // dp[방문상태][현재위치]
// i번 도시를 방문 표시
visited = visited | (1 << i);
// i번 도시를 방문했는지 확인
boolean isVisited = (visited & (1 << i)) != 0;
백엔드/실무에서의 연결
Spring Security 권한 관리
Spring Security의 내부에서 권한 체크 시 비트 연산 개념이 활용됩니다. ACL(Access Control List)에서 permission mask로 비트마스크를 사용합니다.
// Spring Security ACL의 BasePermission
public class BasePermission {
public static final int READ = 1; // 2^0
public static final int WRITE = 1 << 1; // 2^1
public static final int CREATE = 1 << 2; // 2^2
public static final int DELETE = 1 << 3; // 2^3
public static final int ADMIN = 1 << 4; // 2^4
}
해시 함수와 비트 연산
HashMap의 해시 함수에서 비트 연산이 핵심적으로 사용됩니다.
// HashMap의 해시 분산 (Java 내부)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 버킷 인덱스 계산: (n - 1) & hash → n이 2의 거듭제곱이면 모듈러 연산과 동일
네트워크 서브넷 마스크
IP 주소와 서브넷 마스크의 AND 연산으로 네트워크 주소를 구합니다.
IP: 192.168.1.100 → 11000000.10101000.00000001.01100100
Mask: 255.255.255.0 → 11111111.11111111.11111111.00000000
AND: 192.168.1.0 → 11000000.10101000.00000001.00000000
주의할 점
Java에서 int 음수의 우측 시프트 연산
>> 연산자는 부호 비트를 유지하는 산술 시프트입니다. 음수를 우측 시프트하면 상위 비트가 1로 채워집니다. 부호 무시가 필요하면 >>> (논리 시프트)를 사용해야 합니다.
비트마스크에서 int 범위를 초과하는 실수
Java의 int는 32비트이므로 1 << 31은 음수가 됩니다. 원소가 32개 이상이면 long을 사용해야 하고, 1L << i로 리터럴도 long으로 지정해야 합니다.
정리
| 연산 | 기호 | 핵심 용도 |
|---|---|---|
| AND | & | 특정 비트 확인, 마스킹 |
| OR | | | 비트 켜기, 플래그 설정 |
| XOR | ^ | 비트 토글, 중복 원소 찾기 |
| NOT | ~ | 비트 반전, 플래그 해제와 함께 사용 |
| LEFT SHIFT | << | 2의 거듭제곱 곱셈, 비트마스크 생성 |
| RIGHT SHIFT | >> | 2로 나누기 |
기억할 포인트:
n & 1로 짝홀수,n & (n-1) == 0으로 2의 거듭제곱을 판별합니다.- 플래그 패턴으로 여러 상태를 하나의 정수로 관리할 수 있습니다.
- Java에서는
EnumSet이 비트마스크를 우아하게 감싸줍니다. HashMap의 버킷 인덱스 계산, 네트워크 서브넷 마스크 등 실무 곳곳에서 비트 연산이 사용됩니다.
댓글 로딩 중...