비트 연산

비트(bit)

컴퓨터는 숫자를 0과 1로만 표현합니다.

• 0/1 하나를 비트(bit) 라고 합니다.
• 여러 비트가 모이면 숫자가 됩니다.

예를 들어 십진수 5는 이진수로 101입니다.

• 101을 오른쪽부터 보면
  • 1의 자리(2^0) = 1
  • 2의 자리(2^1) = 0
  • 4의 자리(2^2) = 1

즉 101 = 4 + 1 = 5

 

이진수는 “2의 거듭제곱 자리”로 숫자를 표현한 것이라고만 생각하시면 됩니다.

 

---

 

“i번째 비트”

숫자를 이진수로 썼을 때, 오른쪽 끝부터 0번째 비트라고 부릅니다.

예: 13 = 1101

• 0번째 비트: 1
• 1번째 비트: 0
• 2번째 비트: 1
• 3번째 비트: 1

 

---

비트 연산자 

AND (&) — 둘 다 1이면 1

a	b	a&b
0	0	0
0	1	0
1	0	0
1	1	1

 

 OR (|) — 하나라도 1이면 1

a	b	a|b
0	0	0
0	1	1
1	0	1
1	1	1

 

---

오른쪽 시프트 (>>) — 비트를 오른쪽으로 민다

a >> i 는 오른쪽 시프트(>>) = 비트를 오른쪽으로 한 칸씩 밀고 왼쪽 빈칸은 0으로 채운다

예: 13(1101) >> 1 = 6(0110)

 

오른쪽으로 1칸 밀기

기존: 1 1 0 1 ↓ ↓ ↓ 이동: 0 1 1 0

• 맨 오른쪽 1 → 버려짐
• 왼쪽에 빈칸 생김 → 0으로 채움

 

결과: 0110 (십진수 6)

13 >> 1 === 6

이번엔 2칸 밀어봅니다.

1칸 밀기 1101 → 0110

다시 1칸 밀기 0110 → 0011

결과: 0011 (십진수 3)

그래서 13 >> 2 === 3

 

 

마지막 비트만 뽑기: & 1

x & 1은 x의 맨 오른쪽 비트가 1인지(홀수인지) 확인하는 데 자주 씁니다.

• 6(110) & 1 = 0
• 7(111) & 1 = 1

 

---

i번째 비트를 뽑는 공식: (n >> i) & 1

const bit = (n >> i) & 1; // i번째 비트가 0인지 1인지

 

1. n >> i로 i번째 비트를 맨 끝으로 끌고 온 뒤
2. & 1로 맨 끝만 남기기 때문입니다.

 

 

 

 

---

예시 LeetCode 1318: Minimum Flips to Make a OR b Equal to c

문제 요약

정수 a, b, c가 있을 때,

• a | b의 결과가 c와 같아지도록
• a 또는 b의 비트를 뒤집는(flip) 최소 횟수를 구합니다.

flip은 간단히:

• 0 -> 1 또는 1 -> 0로 바꾸는 것

 

비트 문제 대부분은 0번째 자리부터 31번째 자리까지 각각 따로 맞추는 문제

왜 32번(0~31) 보나요?

TypeScript/JavaScript에서 비트 연산자는 숫자를 32비트 정수로 변환해서 연산합니다.
그래서 보통 0~31비트를 검사하는 루프를 씁니다.

---

자리별 경우의 수

각 비트 자리에서

• aBit : a의 i번째 비트
• bBit : b의 i번째 비트
• cBit : c의 i번째 비트

를 꺼내서 생각합니다.

그리고 OR 결과는

• orBit = aBit | bBit

이미 맞으면 flip 0

• orBit === cBit이면 아무 것도 할 필요가 없습니다.

cBit이 0이어야 한다면?

• OR이 0이 되려면 aBit=0 AND bBit=0이어야 합니다.
• cBit = 0인데 orBit = 1이 나왔다?
  • 그 말은 aBit나 bBit 중 적어도 하나가 1이라는 뜻
  • 1인 비트들을 모두 0으로 꺼야 합니다.

aBit	bBit	orBit	cBit	필요한 flip
1	1	1	0	2 (둘 다 꺼야 함)
1	0	1	0	1 (a만 끔)
0	1	1	0	1 (b만 끔)

 

그래서 코드에서

flips += aBit + bBit;

가 되는 겁니다.

• aBit/bBit는 0 또는 1
• 둘 중 켜져 있는(1) 개수만큼 끄면 됩니다.

Bit이 1이어야 한다면?

OR이 1이 되려면 aBit 또는 bBit 중 하나만 1이면 됩니다.

• cBit = 1인데 orBit = 0이 나왔다?
  • 그 말은 aBit=0이고 bBit=0이라는 뜻
  • 둘 중 하나만 1로 켜면 되므로 flip 1

 

코드 

function minFlips(a: number, b: number, c: number): number {
  let flips = 0;

  for (let i = 0; i < 32; i++) {
    const aBit = (a >> i) & 1;
    const bBit = (b >> i) & 1;
    const cBit = (c >> i) & 1;

    const orBit = aBit | bBit;

    // 이미 이 자리(i번째 비트)가 맞으면 스킵
    if (orBit === cBit) continue;

    // cBit이 0이어야 하면: 켜져있는 비트를 전부 꺼야 함
    if (cBit === 0) {
      flips += aBit + bBit;
    } else {
      // cBit이 1이어야 하면: 둘 다 0인 상태이므로 하나만 켜면 됨
      flips += 1;
    }
  }

  return flips;
}