기술면접 — 비트조작(비트마스크, 비트연산)

What(정의)와 WHY(왜)를 중심으로 공부하기 — 알고리즘(4)

참고

파이썬 알고리즘 인터뷰

HISTORY

원래 비트를 조작하는 것은 하드웨어와 관련이 깊다. 1937년 클로드 섀넌은 전기회로 스위치의 on/off를 이용한 스위칭 회로를 연구하면서, true, false의 2개 값으로 논리 연산을 설명하는 부울 대수를 회로에 적용했고, 논리 게이트를 만들어냈다.

WHAT

인간이 쓰는 정수를 이진수와 이진수 연산법을 통해서 문제를 해결하는 기술을 비트마스크라고 한다.

WHY

참고 링크

• 비트 연산을 하는 가장 큰 이유는 연산 속도다. bit는 최소 정보 단위로 다른 추상화된 정보들과 다르게 즉시 해석되어 전달되므로 연산 속도가 매우 빠르다는 장점이 있다.
• 제어에 뛰어난 성능을 발휘한다. 레지스터의 직접 접근을 통해 bit 레벨 조작이 가능하다.
• 비트 연산을 응용하면 복잡한 로직도 비교적 짧은 코드로 만들 수 있으며, 메모리의 최적화가 가능하다.

HOW

• 10진수와 이진수 변환 → bin(10진수), int(‘2진수 문자열’, 2)
• 비트 논리연산자
  → AND 연산: &
  → OR 연산: |
  → XOR 연산: ^
  → NOT 연산: ~
• 시프트 연산자
  → << n 왼쪽으로 n번 이동 (* 2^n의 효과)
  → >> n 오른쪽으로 n번 이동 (/ 2^n의 효과)
• 비트 마스크 사용: bin(0xF) = 0b1111
• 2의 보수 수학 연산: 비트 연산자 NOT에서 1을 더한 것