비트 연산 (Bit Manipulation)
쉽게 풀면
우리는 평소 숫자를 10진수(0~9)로 다루지만, 컴퓨터 내부에서는 모든 숫자가 0과 1로만 이루어진 비트의 나열로 저장되어 있습니다. 비트 연산은 이 0과 1을 직접 켜고 끄듯이 조작하는 방식입니다. 예를 들어 전등 스위치 여러 개가 나란히 있다고 생각해보면, 특정 스위치만 켜거나(OR), 특정 스위치만 끄거나(AND), 전부 반전시키는(XOR) 것처럼 비트를 다룰 수 있습니다. 이런 연산은 회로 수준에서 바로 처리되기 때문에 곱셈이나 나눗셈, 조건 분기보다 훨씬 빠르며, 짝수·홀수 판별이나 두 배·절반 계산(왼쪽/오른쪽 시프트) 같은 작업을 매우 효율적으로 처리할 수 있습니다.
왜 중요한가
비트 연산은 CPU가 가장 적은 명령어로 처리할 수 있는 기본 연산이기 때문에, 성능이 핵심 평가 지표인 연구 분야에서 반복적으로 등장합니다. 알고리즘 논문에서는 상태 집합을 비트마스크로 압축해 동적 계획법의 탐색 공간을 줄이는 용도로, 시스템·임베디드 논문에서는 메모리와 전력이 제한된 환경에서 연산을 최소화하는 용도로 쓰입니다. 또한 암호학이나 네트워크 프로토콜처럼 데이터를 바이트·비트 단위로 직접 다뤄야 하는 분야에서는 비트 연산이 알고리즘 설계의 근간을 이루기도 합니다. 이런 이유로 논문의 성능 개선을 설명하는 대목에서 비트 연산 기반 최적화가 자주 언급됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 여러 항목이 포함되었는지 여부를 하나하나 반복문으로 확인하는 대신, 각 항목을 비트 하나에 대응시켜 AND·OR·XOR 같은 비트 연산 몇 번으로 한꺼번에 처리했더니 속도가 크게 빨라졌다는 뜻입니다. 조합 최적화, 임베디드 시스템, 저수준 성능 최적화 연구에서 자주 등장합니다.
여기서는 동적 계획법에서 방문 여부나 선택 여부 같은 상태를 하나하나 배열로 저장하는 대신, 비트 하나하나에 대응시켜 정수 하나로 압축했다는 의미입니다. 상태 전이도 반복문 대신 시프트·AND 연산으로 처리해 계산과 메모리 사용을 함께 줄이는 방식으로, 조합 최적화나 그래프 알고리즘 논문에서 흔히 볼 수 있습니다.
네트워크·시스템 분야 논문에서는 제한된 바이트 안에 여러 개의 참/거짓 옵션을 담아야 할 때 이런 표현이 자주 나옵니다. 옵션 하나마다 별도의 필드를 두는 대신 비트 하나씩을 할당해 저장 공간을 아끼고, 확인할 때도 AND 연산 한 번이면 되므로 처리 속도가 빠릅니다.
조금 더 깊게 보면
비트 연산 관련 논문을 읽다 보면 AND·OR·XOR·NOT 같은 기본 연산 외에도 왼쪽/오른쪽 시프트(<<, >>), 비트마스크(bitmask), 그리고 popcount(비트 중 1의 개수를 세는 연산) 같은 용어가 자주 함께 나옵니다. 비트마스크는 여러 참/거짓 값을 정수 하나에 압축해 담는 표현 방식으로, 상태 공간을 다루는 알고리즘(비트 DP)이나 옵션 플래그 표현에 두루 쓰입니다. 성능을 논할 때는 대체로 시간복잡도 감소나 메모리 사용량 감소를 함께 근거로 제시하는 경우가 많으며, 실제 효과는 하드웨어와 컴파일러 최적화 수준에 따라 달라질 수 있다는 점도 함께 고려해야 합니다.
주의할 점
비트 연산은 실행 속도는 빠르지만 코드의 의미를 한눈에 파악하기 어려워 가독성이 떨어지는 경우가 많습니다. 그래서 실무에서는 시간복잡도와 빅오 표기법상 이미 충분히 빠른 부분까지 굳이 비트 연산으로 바꾸기보다는, 성능이 실제로 병목이 되는 곳에만 제한적으로 적용하는 것이 일반적입니다.