[Algorithm] 비트 연산자를 사용한 간단한 알고리즘 (JS)

우선 비트 연산자에 대한 설명이 필요하면 아래 게시물을 참고한다.

[JavaScript] 비트 연산자

---

1️⃣ 짝수를 판별하는 함수

const isEven = (num) => (num & 1) === 0;

isEven(4); // true
isEven(5); // false

 

AND 논리 연산자(&)는 비교하는 비트가 모두 1이면 1을 반환한다.

짝수인 4와 1을 AND 논리 연산자(&)로 비교하면 아래와 같이 0이 나온다.

// 0100 => 4
// 0001 => 1
// 0000 => 0

 

하지만 홀수인 5와 1을 AND 논리 연산자(&)로 비교하면 아래와 같이 1이 나온다.

// 0101 => 5
// 0001 => 1
// 0001 => 1

 

💡 isEven() 함수의 원리는 10진수인 숫자를 2진수로 나타내 마지막 비트가 1인지 0인지를 판별해 짝/홀수를 구분한다.

---

2️⃣ 양수를 판별하는 함수

const isPositive = (num) => {
  if (num === 0) return false;
  return ((num >> 31) & 1) === 0;
}

isPositive(5); // true
isPositive(-5); // false

 

오른쪽 시프트 연산자(>>)는 지정한 수만큼 비트 전체를 오른쪽으로 이동하고, 오른쪽에 있는 비트는 소멸된다.

양수인 5를 이진수로 변환하여 31만큼 오른쪽으로 이동하면 0이 나온다.

// 5 : 0000 0000 0000 0000 0000 0000 0000 0101
// 0 : 0000 0000 0000 0000 0000 0000 0000 0000

 

하지만 음수인 -5를 이진수로 변환하여 31만큼 오른쪽으로 이동하면 -1이 나온다.

// -5 : 1111 1111 1111 1111 1111 1111 1111 1010
// -1 : 1111 1111 1111 1111 1111 1111 1111 0001

 

그리하여 0 & 1은 0이 나오고 -1 & 1은 1이 나오기 때문에 양/음수를 구분할 수 있다.

 

💡 비트를 31만큼 이동하는 이유

자바스크립트는 비트 단위 연산을 할 경우 32비트 int를 기준으로 연산하기 때문에 31만큼 이동한다.

---

3️⃣ 양/음수 변환하는 함수

const switchNum = (num) => ~num + 1;

switchNum(18); // -18
switchNum(-18); // 18

 

부정 논리 연산자(~)는 비트를 반전시켜 양수이면 음수를, 음수이면 양수를 나타낸다.

18을 이진수로 나타내 비트를 반전시켜 십진수로 나타내면 -19가 나온다.

그래서 +1을 하여 18을 -18로 나타낼 수 있다.

// 0000 0000 0000 0000 0000 0000 0001 0010 => 18
// 1111 1111 1111 1111 1111 1111 1110 1101 => -19

 

마찬가지로 -18에 부정 논리 연산자(~)를 적용시키면 17이 나오기 때문에 +1을 해야한다.

// 1111 1111 1111 1111 1111 1111 1110 1110 => -18
// 0000 0000 0000 0000 0000 0000 0001 0001 => 17

---

4️⃣ 2의 거듭제곱인지 확인하는 함수

const isPowerOfTwo = (num) => (num & (num - 1)) === 0;

isPowerOfTwo(4); // true
isPowerOfTwo(5); // false

 

2의 거듭제곱인 4와 4에서 1을 뺀 3을 AND 논리 연산자(&)로 비교하면 0이 나오고,

2의 거듭제곱이 아닌 5와 5에서 1을 뺀 4을 AND 논리 연산자(&)로 비교하면 4이 나온다.

그래서 2의 거듭제곱인 4는 true가 출력되고, 2의 거듭제곱이 아닌 5는 false가 출력된다.

// 4 & (4-1)
// 0100 => 4
// 0011 => 3
// 0000 => 0

// 5 & (5-1)
// 0101 => 5
// 0100 => 4
// 0100 => 4

 

💡 isPowerOfTwo() 함수는 어떤 원리일까?

아래 2의 거듭제곱인 경우의 예시를 보며 규칙을 찾아보자.

// 4 & (4-1)
// 0100 => 4
// 0011 => 3

// 8 & (8-1)
// 1000 => 8
// 0111 => 7

// 16 & (16-5)
// 10000 => 16
// 01111 => 15

 

이진수는 2의 거듭제곱을 통해 0과 1로 나타낸 수이다.

그렇다보니 십진수 4를 이진수로 나타내면 0100, 십진수 8을 이진수로 나타내면 1000처럼

1을 기준점으로 오른쪽 비트는 0으로만 구성되어 있다.

마찬가지로 3(4-1)을 이진수로 나타내면 0011, 7(8-1)을 이진수로 나타내면 0111로

2의 거듭제곱을 이진수로 나타낸 것의 1을 기준으로 오른쪽 비트가 모두 1로 구성되어 있다.

그래서 2의 거듭제곱과 2의 거듭제곱에서 -1한 숫자를 AND 논리 연산자(&)로 비교하면 0이 나올 수 밖에 없다.