[JS] Bitwise 비트 연산자 톺아보기 (feat. 비트마스크)

비트 연산자는 정수의 이진 표현, 즉 비트(0과 1) 단위로 계산하는 연산자다. 주로 성능 최적화, 메모리 절약, 알고리즘 구현 등에서 사용한다. 자바스크립트는 64비트 부동소수점 형식으로 숫자를 저장하지만, 비트 연산을 수행할 땐 내부적으로 피연산자를 32비트 정수로 변환한다. 이는 비트 연산이 정수에만 적용되기 때문. 변환 과정에서 소수부는 버려지고 32비트 정수만 연산에 사용된다.

 

가장 왼쪽에 있는 비트는 부호 비트로 사용되며, 0은 양수 1은 음수를 나타낸다

 

2의 보수 표현법

---

2의 보수 표현법은 비트를 이용해 음수를 나타내는 표준 방식으로, 정수의 이진 표현에서 모든 비트를 반전시킨 후(1의 보수) 1을 더하는 방식으로 계산한다. 즉, 1의 보수에 1을 더하면 2의 보수가 된다.

 

이때 최상위 비트(Most Significant Bit; 부호 비트; 가장 왼쪽에 있는 비트)가 0이면 양수, 1이면 음수를 나타낸다. 2의 보수 표현법은 음수를 나타내는 방식이므로 양수는 이진수 표현을 그대로 사용한다.

 

음수 -5를 2의 보수로 표현하는 과정은 아래와 같다.

 

❶ 절대값(5)의 이진 표현을 구한다.

 

❷ 1의 보수로 변환: 모든 비트를 반전 시킨다.

가장 왼쪽에 있는 부호 비트가 1이므로 음수를 나타낸다

❸ 2의 보수로 변환: 반전된 숫자에 1을 더한다. 모든 비트를 반전시켜서 1의 보수를 만들면 원래 절대값에서 1이 감소하게 된다(5 → 4). 이를 보완하기 위해 1을 더하는 것.

 

반대로 2의 보수로 표현된 음수를 10진수로 변환할 땐, ①모든 비트를 반전 시킨 후(1의 보수로 변환) ②1을 더한 다음(2의 보수로 변환) ③10진수로 변환한다. 마지막으로 ④결과값에 음수 부호를 추가한다.

 

 

비트 연산자

---

AND, OR, XOR 예시는 편의를 위해 4비트로만 표현했다. e.g. 5₍₁₀₎ → 0101₍₂₎

 

AND &

특정 비트를 확인하거나 0으로 설정할 때 자주 사용 (비트마스크에선 교집합)

 

두 피연산자의 각 비트를 비교하여 둘 다 1이면 1 반환, 아니면 0 반환(곱연산).

const result = 5 & 3; // 1

 

 

AND 연산은 비트마스크 집합 연산에서 특정 비트를 포함했는지 여부를 검사할 때 사용한다. 비트마스크는 2진수의 각 비트를 조작하여 특정한 상태나 값을 표현하는 방법이다.

let set = 10; // 2진수 1010
let flag = 8; // 2진수 1000

console.log((set & flag) === flag); // true

/*
  1010 (set) - 1010은 1000과 10을 합한 것과 같다
& 1000 (flag)
------
  1000 (결과)
*/

 

OR |

여러 비트 플래그를 결합할 때 자주 사용 (비트마스크에선 합집합)

 

두 피연산자의 각 비트를 비교하여 하나라도 1이면 1 반환, 둘 다 0이면 0 반환(합연산).

const result = 5 | 3; // 7

 

 

OR 연산은 비트마스크 집합 연산에서 특정 비트를 추가할 때 사용한다.

let set = 8; // 2진수 1000
let flag = 2; // 2진수 0010 (편의를 위해 4비트로 표현)

set = set | flag; // set 집합에 flag 추가
console.log(set); // 10 (2진수 1010)

/*
  1000 (set)
| 0010 (flag)
------
  1010 (결과)
*/

 

만약 {1, 2, 3, 4, 5} 집합에서 1, 3, 5를 부분 집합을 선택하여 비트마스크로 표현하면 21(2진수 10101)이 된다. 즉, 21은 0번째, 2번째, 4번째 비트가 설정된 것을 의미한다. 비트 연산은 O(1) 상수 시간 안에 수행되기 때문에 부분 집합을 더 빠르고 효율적으로 조작할 수 있다.

let set = 0;
set = set | (1 << 4); // 4번 인덱스(5) 추가 -> 10000 (10진수 16)
set = set | (1 << 2); // 2번 인덱스(3) 추가 -> 10100 (10진수 20)
set = set | (1 << 0); // 0번 인덱스(1) 추가 -> 10101 (10진수 21)

// {1, 3, 5} 집합을 비트마스크로 표현하면 10101(10진수 21)이 된다

 

XOR ^

두 값의 차이점을 찾거나 비트를 토글할 때 자주 사용

 

두 피연산자의 각 비트를 비교하여 서로 다르면 1 반환, 같으면 0 반환. 각 비트에 대한 비교는 두 비트를 더한 뒤 mod(나머지 연산) 2 한 것과 같다.

const result = 5 ^ 3; // 6

 

 

NOT ~

특정 비트를 0으로 설정할 때 자주 사용

 

NOT 연산자는 피연산자의 모든 비트를 반전시킨다. (1 → 0, 0 → 1)

const result = ~5; // -6

 

어떤 수 x에 NOT 비트 연산을 하면 -(x + 1)의 결과를 도출한다. 예를들어 ~5는 -(5 + 1) = -6으로 계산된다. 2의 보수 표현법에선 모든 비트를 반전시키고 1을 더하지만, NOT 비트 연산에선 1을 더하는 단계가 없다. 따라서 NOT 연산자의 결과는 1의 보수와 동일하며, 2의 보수에서 1을 뺀 것과도 같다.

 

$$-(x+1) = -x-1$$

 

❶ 절대값(5)을 32비트 이진 표현으로 변환

 

❷ NOT 연산 수행 (비트 반전; 1의 보수로 변환)

가장 왼쪽에 있는 부호 비트가 1이므로 음수를 나타낸다

❸ 10진수로 변환: 2번에서 반전된 비트의 결과는 2의 보수 표현법에서 음수를 나타낸다. 따라서 음수를 표현하기 위해 모든 비트를 다시 반전하고 1을 더해서 2의 보수로 변환하는 과정이 필요하다.

① 모든 비트 반전

② 2의 보수로 변환

③ 10진수 변환 후 음수부호 추가

❶ -5는 음수이므로 2의 보수로 변환

 

❷ NOT 연산 수행 (비트 반전)

가장 왼쪽에 있는 부호가 0이므로 양수를 나타낸다

❸ 10진수로 변환 (2번에서 반전된 비트는 양수를 나타내므로 그대로 10진수로 변환)

 

NOT 연산은 비트마스크 집합 연산에서 AND 연산자와 함께 사용하여 특정 비트를 삭제할 때 사용한다.

let set = 10; // 2진수 1010
let flag = 2; // 2진수 0010 (편의를 위해 4비트로 표현)

set = set & ~flag; // set 집합에서 flag 제거
console.log(set); // 8 (2진수 1000)

/*
  1010 (set)
& 1101 (~flag) - flag를 반전시킨 결과
-------------
  1000 (결과)
*/

 

LEFT SHIFT <<

새로운 비트를 추가하거나 2의 거듭제곱을 곱할 때 자주 사용

 

첫 번째 피연산자의 비트를 두 번째 피연산자가 지정한 횟수만큼 왼쪽으로 이동시킨다. 왼쪽에 초과된 비트는 버려지고, 오른쪽에 생긴 빈 공간은 이동한만큼 0으로 채운다.

const result = 5 << 3; // 40 (5×2×2×2와 동일)

 

왼쪽 시프트 연산은 각 비트를 왼쪽으로 1칸 이동할 때마다 2를 곱하는 것과 같다. 예를들어 2진수 10(10진수 2)을 왼쪽으로 한 칸 이동시키면 100(10진수 4)이 된다. 따라서 x << n 연산은 x × 2ⁿ 과 같다.

 

정리하면 LEFT SHIFT 연산을 1회 진행할 때마다 이진수 가장 오른쪽에 0이 하나 더 붙는다고 보면 된다.

 

RIGHT SHIFT >>

2의 거듭제곱으로 나눌 때 자주 사용

 

💡 2진수 길이와 같거나 더 많은 비트를 오른쪽으로 이동시키면 결과는 항상 0이 된다. 예를들어 2진수 11을 오른쪽으로 한 번 시프트하면 01이 되고, 한 번 더 시프트하면 0이 된다.

 

첫 번째 피연산자의 비트를 두 번째 피연산자가 지정한 횟수만큼 오른쪽으로 이동시킨다. 오른쪽에 초과된 비트들은 버려지고, 왼쪽에 생긴 빈 공간은 기존 최상위 비트(부호 비트)의 복사본으로 채워진다.

const result = 5 >> 3; // 0

 

오른쪽 시프트 연산은 각 비트를 오른쪽으로 1칸 이동할 때마다 2를 나누는 것과 같다. 예를들어 2진수 100(10진수 4)을 오른쪽으로 한 칸 이동시키면 010(10진수 2)가 된다. 따라서 x >> n 연산은 x / 2ⁿ 과 같다.

 

정리하면 RIGHT SHIFT 연산을 1회 진행할 때마다 이진수 가장 오른쪽이 하나씩 잘린다고 보면 된다.

 

UNSIGNED RIGHT SHIFT >>>

양수 결과를 보장하면서 2의 거듭제곱으로 나눌 때 자주 사용

 

첫 번째 피연산자의 비트를 두 번째 피연산자가 지정한 횟수만큼 오른쪽으로 이동시킨다. 오른쪽에 초과된 비트는 버려지고, 왼쪽에 생긴 빈 공간은 부호 비트와 상관없이 0으로 채운다. 때문에 항상 양수 결과를 생성한다.

const result = 5 >>> 3; // 0

 

오른쪽 시프트 연산과 마찬가지로 각 비트를 오른쪽으로 1칸 이동할 때마다 2로 나누는 것과 같다. 따라서 x >>> n 연산은 x / 2ⁿ 과 같다.

 

 

미립자 팁

---

0b(2진수), 0o(8진수), 0x(16진수) 접두사를 이용해 진수를 표현할 수 있다. 참고로 파이썬에서도 자바스크립트와 동일한 접두사를 사용한다. C/C++, Java 에선 8진수에 사용하는 0 접두사만 다르고 나머진 동일하다.

const binary = 0b1100100; // 2진수
const octal = 0o144; // 8진수
const hex = 0x64 // 16진수

console.log(binary, octal, hex); // 100, 100, 100

console.log(binary === 100); // true
console.log(octal === 100); // true
console.log(hex === 100); // true

 

 

레퍼런스

---

2의 보수 계산기 | yeecord

식 및 연산자 - JavaScript | MDN

 

---

글 수정사항은 노션 페이지에 가장 빠르게 반영됩니다. 링크를 참고해 주세요