
비트 조작(Bit Manipulation): 0과 1로 마법을 부리는 기술
비트 연산이 왜 필요할까? 홀짝 판별부터 XOR 스왑, 블룸 필터의 원리, 엔디안(Endianness), 그리고 리액트의 우선순위 관리까지. 로우 레벨 최적화의 핵심을 깊이 있게 다룹니다.

비트 연산이 왜 필요할까? 홀짝 판별부터 XOR 스왑, 블룸 필터의 원리, 엔디안(Endianness), 그리고 리액트의 우선순위 관리까지. 로우 레벨 최적화의 핵심을 깊이 있게 다룹니다.
내 서버는 왜 걸핏하면 뻗을까? OS가 한정된 메모리를 쪼개 쓰는 처절한 사투. 단편화(Fragmentation)와의 전쟁.

미로를 탈출하는 두 가지 방법. 넓게 퍼져나갈 것인가(BFS), 한 우물만 팔 것인가(DFS). 최단 경로는 누가 찾을까?

이름부터 빠릅니다. 피벗(Pivot)을 기준으로 나누고 또 나누는 분할 정복 알고리즘. 왜 최악엔 느린데도 가장 많이 쓰일까요?

매번 3-Way Handshake 하느라 지쳤나요? 한 번 맺은 인연(TCP 연결)을 소중히 유지하는 법. HTTP 최적화의 기본.

많은 웹 개발자들이나 앱 개발자들이 이렇게 생각합니다. "요즘 세상에 누가 비트를 직접 건드려? 컴파일러가 알아서 다 해주는데." "메모리가 부족한 것도 아닌데 굳이 비트 단위로 아껴야 하나?"
반은 맞고 반은 틀린 말입니다. 물론 현대의 고수준 언어(High-Level Language)에서는 비트를 직접 다룰 일이 적습니다. 우리가 int가 4바이트인지 8바이트인지 몰라도 코딩하는 데 지장이 없으니까요.
하지만 성능이 극한으로 중요한 상황이나, 데이터를 효율적으로 압축해야 하는 상황에서는 여전히 비트 조작(Bit Manipulation)이 강력한 무기가 됩니다.
Scheduler 패키지에서 업데이트의 우선순위(Lane)를 관리할 때, 각 Lane을 비트 플래그로 표현하여 어떤 업데이트가 더 급한지 빠르게 계산합니다.오늘은 이 0과 1의 세계에서 벌어지는 마법, 비트 조작에 대해 아주 깊고 자세하게 파헤쳐 봤습니다.
우리가 흔히 아는 &&, ||는 논리 연산자입니다. 비트 연산자는 각 비트 단위로 연산을 수행합니다.
자바스크립트나 파이썬, 자바 등 모든 언어에서 이 연산자들을 기본적으로 지원합니다.
| 연산자 | 기호 | 설명 | 예시 (A=5 0101, B=3 0011) | 결과 |
|---|---|---|---|---|
| AND | & | "둘 다 참이어야 참" (교집합) | 0101 & 0011 | 0001 (1) |
| OR | ` | ` | "하나라도 참이면 참" (합집합) | `0101 |
| XOR | ^ | "서로 다르면 참" (청개구리) | 0101 ^ 0011 | 0110 (6) |
| NOT | ~ | "반대로 뒤집기" (보수) | ~0101 | 1010 (-6, 2의보수) |
| Left Shift | << | 왼쪽으로 밀기 (x 2의 n승) | 0011 << 2 | 1100 (12) |
| Right Shift | >> | 오른쪽으로 밀기 (/ 2의 n승) | 0101 >> 1 | 0010 (2) |
>> vs >>>)자바나 자바스크립트에는 >>> 연산자가 하나 더 있습니다.
>> (Arithmetic Shift): 부호 비트(MSB)를 유지하면서 밉니다. 음수는 계속 음수로 남습니다.>>> (Logical Shift): 빈자리를 무조건 0으로 채웁니다. 음수를 밀면 아주 큰 양수가 되어버립니다. 바이너리 데이터를 다룰 때는 주로 이걸 씁니다.이 부분이 핵심입니다. "이걸 어디다 써?"에 대한 대답들입니다.
보통 x % 2 == 1을 씁니다. 하지만 비트 연산이 더 빠릅니다. (컴파일러가 최적화해주긴 하지만요).
2진수에서 홀수는 맨 마지막 비트(LSB)가 무조건 1입니다.
101), 7 (111), 9 (1001)// Good
if (x & 1) {
console.log("홀수입니다");
} else {
console.log("짝수입니다");
}
어떤 수가 $2^n$인지($1, 2, 4, 8, 16...$) 확인하려면 어떻게 해야 할까요? 반복문으로 2로 계속 나눠볼까요? 아닙니다. O(1)에 가능합니다. 2의 거듭제곱 수들은 이진수로 보면 1이 딱 하나만 있습니다.
100011 (4에서 1을 뺀 수)4와 3을 AND 연산하면?
100 & 011 = 000 (0)
공식: x & (x - 1) == 0 (단, x > 0)
이 코드는 루프 없이 단 한 줄로 2의 거듭제곱을 판별합니다. 해시맵(HashMap)의 크기를 2의 배수로 유지해야 할 때(Resizing) 자주 쓰입니다.
임시 변수(temp) 없이 두 변수의 값을 바꾸는 고전적인 트릭입니다. 최근에는 컴파일러 최적화나 가독성 문제로 실제로는 잘 안 쓰지만, 기본기로 유명하며 임베디드 환경에서는 여전히 유효합니다.
int a = 10, b = 20;
a = a ^ b;
b = a ^ b; // (a ^ b) ^ b = a (b가 사라지고 a가 남음)
a = a ^ b; // (a ^ b) ^ a = b (a가 사라지고 b가 남음)
이는 XOR의 성질인 x ^ x = 0과 x ^ 0 = x를 이용한 것입니다.
가장 많이 쓰이는 비트마스킹의 기본기입니다. n번째 비트를 자유자재로 다룰 수 있어야 합니다.
bit & (1 << n)
bit | (1 << n)
bit & ~(1 << n)
bit ^ (1 << n)
리눅스 파일 권한(chmod 755)이나 디스코드 봇 권한 설정이 다 이 방식을 씁니다.
READ, WRITE, EXECUTE, DELETE 같은 권한을 불리언 변수 4개로 만들면 DB 컬럼도 4개 필요하고 관리도 귀찮습니다.
만약 권한이 30개라면요? 컬럼 30개를 만드실 건가요?
비트마스크를 쓰면 INT 하나로 해결됩니다.
const PERM_READ = 1 << 0; // 0001 (1)
const PERM_WRITE = 1 << 1; // 0010 (2)
const PERM_EXECUTE = 1 << 2; // 0100 (4)
const PERM_DELETE = 1 << 3; // 1000 (8)
const PERM_ADMIN = 1 << 4; // 10000 (16)
// 사용자의 권한 초기값 (0)
let myPerm = 0;
// 1. 권한 부여 (READ + WRITE)
myPerm = myPerm | PERM_READ | PERM_WRITE;
// myPerm = 0011 (3)
// 2. 권한 확인 (DELETE 권한이 있나?)
if (myPerm & PERM_DELETE) {
console.log("삭제 가능");
} else {
console.log("삭제 불가"); // 출력됨
}
// 3. 권한 삭제 (WRITE 권한 뺏기)
myPerm = myPerm & ~PERM_WRITE;
// myPerm = 0001 (READ만 남음)
// 4. 권한 토글 (있으면 없애고, 없으면 주고)
myPerm = myPerm ^ PERM_ADMIN;
이 방식은 수십 개의 권한 옵션이 있어도 정수 하나로 관리할 수 있어 DB 공간을 엄청나게 절약하고, 쿼리 속도도 매우 빠릅니다. 백엔드 개발자라면 꼭 알아둬야 할 패턴입니다.
비트마스킹은 동적 계획법(DP)과 결합될 때 강력합니다.
방문한 도시들의 상태를 visited 배열 [true, false, true...] 대신 비트마스크 00101로 표현하여 DP 테이블의 인덱스로 활용합니다.
dp[mask][current] 형태로 상태를 저장하면 메모리와 시간을 획기적으로 줄일 수 있습니다. 정수를 배열 인덱스로 바로 쓸 수 있다는 점이 엄청난 메리트조.
DB 조회 속도를 높이기 위해 사용하는 확률적 자료구조입니다. "이 데이터가 DB에 확실히 없는가?"를 판단하는 데 특화되어 있습니다. 거대한 비트 배열을 만들고, 해시 함수를 여러 개 돌려서 나온 위치의 비트를 1로 셋팅합니다. 나중에 조회할 때 해당 위치들이 모두 1인지 확인합니다. 만약 하나라도 0이면? -> "DB에 절대 없음" (확실). 모두 1이면? -> "있을 수도 있음" (거짓 양성 가능성). 이 원리를 이용해 불필요한 디스크 I/O를 막아줍니다. 레디스(Redis)에서도 지원하는 자료구조입니다.
비트를 다룰 때 꼭 알아야 할 개념이 있습니다. 바로 빅 엔디안(Big Endian)과 리틀 엔디안(Little Endian)입니다.
여러 바이트로 구성된 숫자(예: 32비트 정수 0x12345678)를 메모리에 저장할 때 순서가 다릅니다.
12 34 56 78 (사람이 읽는 순서대로. 네트워크 표준)78 56 34 12 (거꾸로. 인텔/AMD CPU 표준)네트워크 프로그래밍을 할 때 내 컴퓨터(리틀 엔디안)에서 보낸 데이터를 서버(빅 엔디안일 수도 있음)가 다르게 해석할 수 있기 때문에, 전송 전에 ntohl(Network to Host Long) 같은 함수로 변환해줘야 합니다.
게임 개발 역사상 가장 유명한 비트 조작 코드는 Quake III Arena 엔진에서 발견되었습니다.
조명 계산(빛 반사)을 하려면 벡터 정규화가 필요하고, 이때 $1 / \sqrt$ (제곱근의 역수)를 엄청나게 많이 계산해야 했습니다.
당시 CPU로는 sqrt 함수가 너무 느렸습니다(나눗셈은 비쌉니다). 그때 한 천재 개발자가 정신 나간 코드를 작성합니다.
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
return y;
} // 출처: Quake III Arena Source Code
저 0x5f3759df라는 매직 넘버를 사용하여, 부동소수점 비트 구조를 마치 정수처럼 비트 시프트(>> 1)만으로 제곱근 근사값을 구해버립니다.
이 코드는 당시 하드웨어 명령어보다 4배나 빨랐다고 합니다.
이것이 바로 비트 조작이 보여줄 수 있는 극한의 퍼포먼스 튜닝이자, 하드웨어를 완벽하게 이해했을 때 만들 수 있는 예술입니다.
비트 연산을 처음 쓸 때 가장 많이 하는 실수가 바로 우선순위입니다.
C언어나 자바 등에서 비트 연산자(&, |, ^)는 비교 연산자(==, !=)보다 우선순위가 낮습니다.
// 의도: flag의 3번째 비트가 0인지 확인
if (flag & 4 == 0)
위 코드는 어떻게 해석될까요?
4 == 0이 먼저 실행되어 false(0)가 되고, 결국 flag & 0이 되어버립니다. 항상 0(거짓)이 되는 끔찍한 버그가 발생합니다.
()를 치는 습관을 들이세요.
if ((flag & 4) == 0) // 안전!
비트 조작은 겉보기엔 암호 같고 어려워 보입니다. 하지만 그 원리는 속도와 효율성에 대한 집착에서 나왔습니다.
남들이 boolean 컬럼 10개 만들 때, int 컬럼 1개로 처리하는 여러분의 모습을 보며 동료들이 감탄할 것입니다.
물론, "조기 최적화는 만악의 근원(Premature optimization is the root of all evil)"이라는 말처럼, 무턱대고 모든 코드를 비트 연산으로 떡칠하면 가독성만 해칩니다. 하지만 프레임워크 내부를 이해하거나, 대용량 트래픽을 처리하거나, 하드웨어와 가까운 개발을 할 때 비트 조작은 대체 불가능한 필수 역량입니다.
컴퓨터의 가장 밑바닥 언어인 0과 1을 이해하고 다루는 것, 그것이 바로 '코더'를 넘어 진정한 '엔지니어'로 가는 첫걸음입니다.