Ruby 비트 연산 완전 정복: Bitwise 해킹의 세계

일상적인 업무에서 비트 연산(bitwise math)을 직접 할 일은 많지 않을 겁니다. Ruby의 비트 AND(&)와 OR(|) 연산자는 의도적으로 쓰이기보다 실수로 쓰이는 경우가 더 많죠. &&를 쓰려다 &를 잘못 입력해 본 적 없는 개발자는 드물 겁니다.

하지만 C나 어셈블러처럼 저수준 언어로 프로그래밍을 배웠거나, 저처럼 Turbo Pascal 시절을 보낸 사람이라면 비트 조작(bit twiddling)을 한 번쯤은 경험해 봤을 겁니다.

비트 연산으로 문제를 해결하는 건 정말 멋진 일입니다. 컴퓨터가 수행할 수 있는 가장 기본적인 연산, 즉 이진수 계산만으로 문제를 풀어낼 수 있다면 그보다 우아한 방법은 없습니다.

Ruby에서 이진수 다루기

컴퓨터의 모든 것이 숫자로 표현되고, 그 숫자들은 이진수 형태라는 점은 이미 알고 있을 겁니다. 그렇다면 Ruby에서는 어떤 모습일까요? 아래 예제에서는 Ruby로 문자 "a"의 ASCII 코드를 찾아낸 뒤, 이를 이진수로 출력해 봅니다.

Ruby에서는 ord 메서드로 문자의 ASCII 코드를 구하고, printf를 사용해 이진수 표현으로 출력할 수 있습니다.

사실 printf 같은 메서드는 단지 화면에 이진수 형태로 보여줄 뿐입니다. 숫자는 원래부터 항상 이진수였습니다. Ruby 코드 안에서도 0b11111111 같은 문법으로 이진수를 직접 작성할 수 있습니다.

코드에 이진수 리터럴을 추가하려면 0과 1로 이루어진 숫자열 앞에 0b를 붙이기만 하면 됩니다.

이진수 값 조작하기

Ruby에서 이진수 리터럴을 사용하는 방법을 알았으니, 이제 본격적으로 비트를 가지고 놀아볼 차례입니다. 이를 위해 비트 연산자(bitwise operators)를 사용합니다.

논리 연산자인 &&에는 이미 익숙할 겁니다. a && b 표현식은 a와 b가 모두 참일 때만 true를 반환하죠. 비트 연산자도 매우 유사하게 동작합니다.

예를 들어 비트 AND는 두 값을 받아 비트별로 하나씩 비교합니다. 양쪽 비트가 모두 1이면 결과의 해당 비트를 1로 설정하고, 그렇지 않으면 0으로 설정합니다. 즉, 8비트라면 8번의 독립적인 AND 연산이 일어나고, 1비트라면 AND가 한 번 일어나는 셈입니다. 아래 예제는 단일 비트로 이를 보여줍니다.

두 비트에서도 동일하게 동작합니다.

Ruby의 비트 연산자

거의 모든 프로그래밍 언어에는 아래와 같은 비트 연산자들이 포함되어 있습니다. 낯설다면 IRB에서 잠시 실험해 보세요. 한 번 익혀두면 평생 사용할 수 있습니다.

실전 활용: 설정 플래그(Configuration Flags)

솔직히 말씀드리면, 이건 비트 연산의 가장 지루한 활용 사례일 겁니다. 하지만 동시에 가장 널리 쓰이는 용도이기도 합니다. Java, C, C++로 작성된 코드와 연동해야 하는 순간, 언젠가는 반드시 비트 기반 설정 플래그와 마주치게 됩니다.

1996년이라고 상상해 봅시다. 여러분은 방금 데이터베이스 시스템을 처음부터 끝까지 직접 만들었습니다. 영화 <해커즈>를 방금 본 참이라, 어떤 형태로든 접근 제어(access control) 기능을 넣어두는 게 좋겠다고 생각합니다.

여러분의 DB에서 사용자가 수행할 수 있는 행동은 8가지입니다. 읽기(read), 쓰기(write), 삭제(delete), 그리고 나머지 다섯 가지죠. 각 권한을 독립적으로 설정하고 싶습니다. 읽기는 가능하지만 쓰기나 삭제는 못 하는 사용자가 있을 수도 있고, 쓰기는 가능하지만 테이블 DROP은 못 하는 사용자도 있을 겁니다.

이런 설정 플래그들을 저장하는 가장 효율적인 방법은 하나의 바이트 안에 각 권한을 비트로 담는 것입니다. 그리고 필요한 권한 조합을 만들 때는 단순히 OR 연산으로 묶어주면 됩니다.

MYDB_READ   = 0b00000001 # 이 숫자들을 비트마스크(bitmask)라고 부릅니다
MYDB_WRITE  = 0b00000010
MYDB_DELETE = 0b00000100
MYDB_INDEX  = 0b00001000

user.permissions = MYDB_READ | MYDB_WRITE

참고로 이 방식은 Unix 파일 권한이 처리되는 방식과 매우 유사합니다. 파일을 읽기 전용으로 만들려고 할 때 왜 하필 저런 신비한(magic) 숫자를 써야 하는지 궁금했던 적이 있다면, 이제 그 이유를 아시겠죠.

물론 특정 비트가 켜져 있는지 확인할 수 없다면 비트 단위 설정 옵션은 큰 의미가 없습니다. 이때는 그저 비트 AND를 사용하면 됩니다.

덜 실용적인 활용법 (C 프로그래머가 아니라면)

이제 좀 더 마법 같은 수학을 해볼 차례입니다.

역사적으로 비트 조작은 어떤 계산에서 밀리초의 극히 일부라도 더 줄여내야 했을 때 사용됐습니다. 짐작하시겠지만, 그래픽 프로그래머처럼 성능이 그 무엇보다 중요했던 개발자들이 애용했습니다.

따라서 이런 기법들은 일상적인 Ruby 개발에는 크게 실용적이지 않습니다. 하지만 재미있는 학습 과제인 것은 물론이고, 임베디드 시스템 프로그래밍 같은 분야에 발을 들이면 실제로 유용하게 쓸 수 있습니다. 더 깊이 있는 내용이 궁금하다면 유명한 "bit twiddling hacks" 목록을 찾아보시길 추천합니다.

2의 거듭제곱으로 곱셈과 나눗셈하기

숫자 1, 2, 4, 8의 이진수 표현을 살펴봅시다. 보시다시피 숫자를 두 배로 만드는 것은 모든 비트를 한 칸 왼쪽으로 시프트하는 것과 같고, 반으로 나누는 것은 오른쪽으로 시프트하는 것과 같습니다.

기억하시겠지만 우리에게는 왼쪽 시프트와 오른쪽 시프트 연산자가 있습니다. 즉, 비트를 시프트하는 것만으로 2의 거듭제곱을 곱하고 나눌 수 있는 것입니다.

두 양의 정수의 평균 구하기

두 정수의 덧셈은 다음과 같이 비트 연산으로 표현할 수 있습니다: (x+y) == (x&y)+(x|y) == (x^y)+2*(x&y). 평균을 구하려면 여기서 2로 나누기만 하면 되는데, 이는 오른쪽 시프트 연산자로 얻을 수 있습니다.

고속 역제곱근(Fast Inverse Square Root)

비트 조작에 관한 글에서 전설적인 사례 하나를 빼놓을 수는 없겠죠. 바로 1999년 Quake 3 Arena 소스 코드에 등장한 John Carmack의 고속 역제곱근 근사 알고리즘입니다. 알고리즘 자체는 그의 것이 아니지만, 가장 유명한 구현체는 그의 이름과 함께 기억됩니다.

C 코드를 Ruby로 직접 포팅하는 시도는 하지 않겠습니다. 이 코드는 부동소수점 수의 이진 표현을 C 특유의 방식으로 조작하기 때문에 Ruby로 그대로 옮길 수 없기 때문입니다.

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // 사악한 부동소수점 비트 수준 해킹
    i  = 0x5f3759df - ( i >> 1 );               // 대체 무슨 일이 벌어지는 걸까?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 첫 번째 반복
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 두 번째 반복 — 생략 가능

    return y;
}