0Pricing
DSA Interview Prep · 강의

비트 연산자: AND, OR, XOR, NOT, 시프트

진리표와 Python 예제로 여섯 가지 비트 연산자를 모두 복습하고, 왼쪽 및 오른쪽 시프트가 2를 곱하고 나누는 연산과 어떻게 관련되는지 이해합니다.

비트 연산자: AND, OR, XOR, NOT, 시프트은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

비트 조작이 중요한 이유

비트 조작을 사용하면 정수의 이진 표현을 직접 다룰 수 있습니다. 복잡해 보이는 많은 문제가 적절한 비트 연산 요령을 사용하면 간단해집니다. 예를 들어 O(n) 시간과 O(1) 공간으로 누락된 수를 찾거나, 임시 변수 없이 변수를 교환하거나, 부분 집합을 간결하게 인코딩할 수 있습니다. 면접관은 이러한 문제를 통해 저수준 동작에 대한 이해와 창의적인 사고를 평가합니다.

Python의 정수는 임의 정밀도를 지원하므로 메모리가 허용하는 만큼 커질 수 있습니다. 하지만 비트 연산은 하드웨어 수준에서 항상 표준 2의 보수 의미를 따릅니다. 여섯 가지 연산자는 모두 정수의 이진 표현을 비트 단위로 다룹니다.

# All six bitwise operators in Python
a, b = 0b1010, 0b1100  # 10 and 12 in decimal
print(f'a = {bin(a)} = {a}')
print(f'b = {bin(b)} = {b}')
print(f'a & b  (AND) = {bin(a & b)} = {a & b}')   # 1000 = 8
print(f'a | b  (OR)  = {bin(a | b)} = {a | b}')   # 1110 = 14
print(f'a ^ b  (XOR) = {bin(a ^ b)} = {a ^ b}')   # 0110 = 6
print(f'~a     (NOT) = {~a}')                       # -11 (two's complement)
print(f'a << 1 (LSH) = {bin(a << 1)} = {a << 1}') # 10100 = 20
print(f'a >> 1 (RSH) = {bin(a >> 1)} = {a >> 1}') # 101 = 5

AND 연산자: 비트 마스킹

AND 연산자 (&)는 두 입력 비트가 모두 1일 때만 1을 출력합니다. 주요 용도는 마스킹으로, 다른 비트를 모두 0으로 만들면서 수에서 특정 비트만 선택합니다. 수 n에서 비트 k가 설정되어 있는지 확인하려면 n & (1 << k)를 계산하십시오. 결과가 0이 아니면 비트 k는 1입니다.

AND는 가장 낮은 설정 비트 지우기에도 사용됩니다. n & (n - 1)은 가장 오른쪽의 1비트를 제거합니다. 이는 설정된 비트의 개수를 효율적으로 세거나 수가 2의 거듭제곱인지 확인할 때 사용됩니다. 2의 거듭제곱에는 설정 비트가 정확히 하나만 있으므로 n & (n-1) == 0이 됩니다.

n = 0b10110100  # 180

# Check if bit 5 is set (0-indexed from right)
bit_5 = (n >> 5) & 1
print(f'Bit 5 of {n}: {bit_5}')  # 1

# Clear lowest set bit
print(f'n = {bin(n)}')
print(f'n & (n-1) = {bin(n & (n-1))}')  # 10110000, removed the '100'

# Check power of two
for x in [16, 15, 8, 6, 1, 0]:
    is_pow2 = x > 0 and (x & (x - 1)) == 0
    print(f'{x}: power of 2 = {is_pow2}')

OR 연산자: 비트 설정

OR 연산자 (|)는 입력 비트 중 하나 이상이 1이면 1을 출력합니다. 주요 용도는 다른 비트에는 영향을 주지 않고 특정 비트를 1로 설정하는 것입니다. 수 n에서 비트 k를 설정하려면 n | (1 << k)를 사용하십시오. k번째 위치로 시프트된 1이 해당 비트를 켜며, 0과 OR한 값은 그대로 유지되므로 다른 모든 비트는 변하지 않습니다.

OR는 플래그 결합에도 사용됩니다. 기능 플래그를 각각의 비트로 표현하면 OR를 사용해 여러 플래그를 활성화할 수 있습니다. 예를 들어 READ | WRITE | EXECUTE는 세 개의 권한 비트를 하나의 정수로 결합합니다.

# Set bit k in n
def set_bit(n, k):
    return n | (1 << k)

n = 0b1000  # 8
print(f'Original: {bin(n)}')
print(f'Set bit 1: {bin(set_bit(n, 1))}')  # 1010
print(f'Set bit 0: {bin(set_bit(n, 0))}')  # 1001

# Flag combination example
READ    = 0b001  # 1
WRITE   = 0b010  # 2
EXECUTE = 0b100  # 4

perms = READ | EXECUTE
print(f'READ|EXECUTE permissions: {bin(perms)} = {perms}')
print(f'Has READ:    {bool(perms & READ)}')
print(f'Has WRITE:   {bool(perms & WRITE)}')
print(f'Has EXECUTE: {bool(perms & EXECUTE)}')

XOR 연산자: 전환과 차이

XOR 연산자 (^)는 입력 비트가 서로 다를 때 1을 출력합니다. XOR에는 강력한 대수적 성질이 세 가지 있습니다. a ^ a = 0(같은 입력은 서로 상쇄됨), a ^ 0 = a(0은 항등원), 그리고 XOR는 교환 법칙과 결합 법칙을 모두 만족합니다. 이러한 성질 때문에 XOR는 고유한 요소를 찾는 대표적인 도구입니다.

XOR는 특정 비트 전환에도 사용됩니다. n ^ (1 << k)는 다른 비트는 그대로 둔 채 비트 k를 뒤집습니다. 비트 k가 0이었다면 1이 되고, 1이었다면 0이 됩니다.

# XOR properties
print(5 ^ 5)    # 0 — same values cancel
print(5 ^ 0)    # 5 — zero is identity
print(5 ^ 3 ^ 3)  # 5 — 3 cancels itself

# Toggle bit k
def toggle_bit(n, k):
    return n ^ (1 << k)

n = 0b1010
print(f'Toggle bit 3: {bin(toggle_bit(n, 3))}')  # 0010 (was 1)
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}')  # 1011 (was 0)

# XOR swap without temp variable
a, b = 7, 13
a = a ^ b
b = a ^ b   # b now gets original a
a = a ^ b   # a now gets original b
print(f'After XOR swap: a={a}, b={b}')  # a=13, b=7

NOT 연산자와 2의 보수

NOT 연산자 (~)는 모든 비트를 반전합니다. Python에서는 2의 보수 표현 때문에 ~n이 -(n+1)과 같습니다. 이는 많은 사람에게 의외일 수 있습니다. 예를 들어 ~5 = -6이며, 단순히 예상하는 0b11111010이 아닙니다. Python의 정수는 무한 정밀도를 사용하므로 양수의 모든 비트를 뒤집으면 2의 보수에서 음수가 됩니다.

실제로 Python에서 비트 조작을 위해 ~만 단독으로 사용하는 경우는 드뭅니다. 대신 AND와 함께 사용해 특정 비트를 지우거나, 비트 폭을 특정 개수로 제한하는 mask와 함께 ~n & mask를 계산하십시오. 예를 들어 32비트에는 & 0xFFFFFFFF를 사용합니다.

# NOT in Python: ~n = -(n+1)
for n in [0, 1, 5, 127]:
    print(f'~{n} = {~n}')   # all give -(n+1)

# Clear bit k using NOT
def clear_bit(n, k):
    return n & ~(1 << k)

n = 0b1111
print(f'Clear bit 2: {bin(clear_bit(n, 2))}')  # 1011
print(f'Clear bit 0: {bin(clear_bit(n, 0))}')  # 1110

# Limiting to 32-bit with mask
def bitwise_not_32(n):
    return ~n & 0xFFFFFFFF

print(f'32-bit NOT of 5: {bin(bitwise_not_32(5))}')  # 32 zeros then ones

왼쪽 시프트: 2의 거듭제곱으로 곱하기

왼쪽 시프트 연산자 (<<)는 모든 비트를 k개 위치만큼 왼쪽으로 이동하고, 비어 있는 오른쪽 위치를 0으로 채웁니다. 이는 2^k를 곱하는 것과 같습니다. 1만큼 왼쪽으로 시프트하면 값이 2배가 되고, k만큼 왼쪽으로 시프트하면 2^k를 곱한 값이 됩니다.

면접 문제에서 왼쪽 시프트는 비트 마스크를 만들 때 가장 흔히 사용됩니다. 1 << k는 비트 k만 설정된 수를 만듭니다. 개별 비트 설정, 지우기, 전환 및 확인을 비롯한 모든 비트 조작의 기초는 1 << k에서 시작합니다.

# Left shift = multiply by 2^k
n = 1
for k in range(8):
    print(f'1 << {k} = {1 << k}')   # 1,2,4,8,16,32,64,128

# Practical use: creating bitmasks
def bit_mask(k):
    return 1 << k

print(f'\nBitmask for bit 0: {bin(bit_mask(0))}')  # 1
print(f'Bitmask for bit 3: {bin(bit_mask(3))}')  # 1000
print(f'Bitmask for bit 7: {bin(bit_mask(7))}')  # 10000000

# Fast exponentiation: 2^10 = 1024
print(f'2^10 = {1 << 10}')  # 1024

오른쪽 시프트: 2의 거듭제곱으로 나누기

오른쪽 시프트 연산자 (>>)는 모든 비트를 k개 위치만큼 오른쪽으로 이동하고, 가장 오른쪽의 k개 비트를 버립니다. 이는 2^k로 정수 나눗셈을 하는 것과 같습니다. Python의 오른쪽 시프트는 항상 산술 시프트입니다. 가장 왼쪽 비트는 부호 비트로 채워지며, 양수에서는 0, 음수에서는 1이 됩니다.

면접에서 자주 사용하는 요령은 수 n에서 비트 k를 추출할 때 (n >> k) & 1을 사용하는 것입니다. 이렇게 하면 비트 k가 위치 0으로 내려오고 다른 모든 비트가 마스킹됩니다. 전체 마스크를 계산하고 비교하지 않아도 특정 비트를 확인할 수 있는 가장 깔끔한 방법입니다.

# Right shift = integer division by 2^k
n = 64
for k in range(7):
    print(f'{n} >> {k} = {n >> k}')   # 64,32,16,8,4,2,1

# Extract bit k from n
def get_bit(n, k):
    return (n >> k) & 1

n = 0b10110101  # 181
print(f'\nBits of {n} ({bin(n)}):')
for k in range(8):
    print(f'  Bit {k}: {get_bit(n, k)}')

# Negative number right shift (arithmetic)
print(f'-8 >> 1 = {-8 >> 1}')   # -4 (fills with sign bit 1)

실전 비트 연산 요령 모음

다음은 면접에서 접하게 될 가장 일반적인 비트 조작 관용구 모음입니다. 이 패턴들을 외워 두십시오. 수십 가지 문제에서 반복해서 등장합니다.

  • n & 1 — n이 홀수인지 확인
  • n & (n-1) — 가장 낮은 설정 비트 지우기
  • n & -n — 가장 낮은 설정 비트만 추출
  • n | (1 << k) — 비트 k 설정
  • n & ~(1 << k) — 비트 k 지우기
  • n ^ (1 << k) — 비트 k 전환
  • (n >> k) & 1 — 비트 k 확인
# Bit trick cheatsheet — all at once
n = 0b10110100  # 180

print(f'n = {bin(n)} = {n}')
print(f'n & 1       (odd check)         = {n & 1}')          # 0: even
print(f'n & (n-1)   (clear lowest bit)  = {bin(n & (n-1))}')
print(f'n & -n      (isolate lowest bit) = {bin(n & -n)}')
print(f'n | (1<<1)  (set bit 1)          = {bin(n | (1<<1))}')
print(f'n & ~(1<<2) (clear bit 2)        = {bin(n & ~(1<<2))}')
print(f'n ^ (1<<5)  (toggle bit 5)       = {bin(n ^ (1<<5))}')
print(f'(n>>4) & 1  (check bit 4)        = {(n>>4) & 1}')

설정 비트 개수 세기 (팝카운트)

정수에 포함된 1비트의 개수를 세는 것을 population count(팝카운트)라고 합니다. 순진한 방법은 모든 비트를 순회합니다. Brian Kernighan 요령은 다음과 같이 가장 낮은 설정 비트를 반복해서 지우는 더 빠른 방법입니다. n &= n - 1을 사용하고 n이 0이 될 때까지 반복 횟수를 셉니다. 한 번 반복할 때마다 정확히 하나의 1비트가 제거되므로, 반복 횟수는 1비트의 개수와 정확히 같습니다.

Python 3.10 이상에서는 개수를 직접 반환하는 int.bit_count()를 제공합니다. 이전 버전에서는 Kernighan 요령이 표준적인 수동 방법입니다. 이 기법은 LeetCode의 'Hamming Weight' 문제도 해결합니다.

# Method 1: naive O(log n)
def count_bits_naive(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Method 2: Brian Kernighan O(k) where k = number of set bits
def count_bits_fast(n):
    count = 0
    while n:
        n &= n - 1   # clear lowest set bit
        count += 1
    return count

# Method 3: Python built-in (3.10+)
# n.bit_count()

for x in [0, 1, 7, 255, 180, 1024]:
    naive = count_bits_naive(x)
    fast  = count_bits_fast(x)
    print(f'{x:4d} ({bin(x):10s}): naive={naive}, fast={fast}')

Python 비트 조작의 중요한 주의점

C/Java와 달리 Python의 정수는 임의로 큰 값을 가질 수 있습니다. 즉, 32비트 또는 64비트 오버플로가 발생하지 않습니다. 따라서 32비트 동작을 기대하는 문제를 풀 때는 결과를 고정된 비트 폭에 맞게 직접 마스킹해야 합니다. & 0xFFFFFFFF를 사용하면 하위 32비트만 유지할 수 있습니다.

Python의 NOT 연산자 ~n은 C에서 예상할 법한 비트 반전 결과가 아니라 -(n+1)을 반환합니다. 32비트 문제에서는 ~n & 0xFFFFFFFF를 사용하거나 0xFFFFFFFF ^ n을 계산하여 예상되는 32비트 보수를 얻으십시오. 이러한 차이 때문에 C 방식의 비트 조작에 익숙한 많은 응시자가 실수합니다.

# Python vs C gotchas
# In C: unsigned 32-bit NOT of 5 = 4294967290
# In Python: ~5 = -6
print(f'Python ~5 = {~5}')              # -6
print(f'32-bit ~5 = {~5 & 0xFFFFFFFF}') # 4294967290

# No integer overflow in Python
big = 1 << 100   # 2^100: huge number, no overflow
print(f'2^100 = {big}')  # works fine

# Right shift on negatives: arithmetic (sign-extending)
print(f'-1 >> 3 = {-1 >> 3}')   # -1 (all ones shifted in)

# Safe 32-bit mask for problems expecting C/Java semantics
MASK32 = 0xFFFFFFFF
result = (5 + 0xFFFFFFFE) & MASK32  # simulates 32-bit overflow
print(f'5 + (-2) in 32-bit = {result}')  # 3

시프트 연산자와 곱셈

왼쪽 및 오른쪽 시프트는 2의 거듭제곱으로 곱하거나 나누는 매우 빠른 방법을 제공합니다. 하드웨어에서는 비트 시프트가 하나의 명령어로 수행되는 반면, 곱셈과 나눗셈은 여러 사이클이 필요합니다. Python에서는 정수 곱셈이 이미 효율적이지만, 이러한 관계를 이해하면 비트 패턴을 더 명확하게 볼 수 있습니다.

유용한 항등식은 다음과 같습니다. n이 2^k의 배수인지 확인하려면 (n & (2^k - 1)) == 0을 사용하십시오. 마스크 2^k - 1은 하위 k개 비트가 모두 1로 설정되어 있으며, 이 값과 AND하면 2^k로 나눈 나머지를 얻습니다. 이는 n % (2^k)와 같지만 C 기반 언어에서는 더 빠릅니다.

# Shift vs arithmetic equivalence
for k in range(1, 5):
    n = 48
    print(f'{n} * 2^{k} = {n * (2**k)} = {n << k} (left shift)')
    print(f'{n} // 2^{k} = {n // (2**k)} = {n >> k} (right shift)')
    print()

# Check divisibility by power of 2
def divisible_by_power_of_2(n, k):
    mask = (1 << k) - 1   # 2^k - 1: lower k bits all 1
    return (n & mask) == 0

for n in [16, 24, 32, 15, 100]:
    print(f'{n} divisible by 4? {divisible_by_power_of_2(n, 2)}')

빠른 확인

이 레슨에서 배운 자료 구조 및 알고리즘 — 코딩 면접 대비 개념을 제대로 이해했는지 테스트해 보십시오.

레슨 요약

이 레슨에서는 다음을 배웠습니다. AND는 비트를 마스킹하고, OR는 비트를 설정하며, XOR는 비트를 전환하고 차이를 감지하고, NOT은 비트를 반전합니다(Python에서는 -(n+1)을 반환함). 시프트는 2의 거듭제곱으로 곱하거나 나눕니다. n & (n-1)은 가장 낮은 설정 비트를 지우며, 2의 거듭제곱 확인과 비트 개수 세기의 기반이 됩니다. 또한 Python에는 고정된 비트 폭의 오버플로가 없으므로 32비트 문제에서는 & 0xFFFFFFFF를 사용한 명시적 마스킹이 필요합니다. 다음에는 XOR의 자기 역원 성질을 활용하여 단일 숫자 문제 유형을 해결하는 방법을 살펴봅니다.

자주 묻는 질문

“비트 연산자: AND, OR, XOR, NOT, 시프트” 강의는 무료인가요?

네 — “비트 연산자: AND, OR, XOR, NOT, 시프트” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“비트 연산자: AND, OR, XOR, NOT, 시프트”에서 뭘 배우나요?

진리표와 Python 예제로 여섯 가지 비트 연산자를 모두 복습하고, 왼쪽 및 오른쪽 시프트가 2를 곱하고 나누는 연산과 어떻게 관련되는지 이해합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.

“비트 연산자: AND, OR, XOR, NOT, 시프트” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

  1. 비트 연산자: AND, OR, XOR, NOT, 시프트
  2. 단일 숫자와 XOR의 성질
  3. 비트 마스크: 설정, 해제, 전환, 확인
  4. 비트 세기, 누락된 숫자와 비트 뒤집기
← DSA Interview Prep(으)로 돌아가기