---

Reference

• 3460번 이진수, Baekjoon online judge
• 21396번 이진수 더하기, Baekjoon online judge

---

1. 이진법

이진법(binary): 두 개의 숫자(1과 0)만을 이용하는 수 체계.
-Reference.Binary number

1.1. 이진법 알고리즘

• 이진법 계산: $11$을 이진수로 변환하면 $1011 = 2^0 \times 1 + 2^1 \times 1 + 2^2 \times 0 + 2^3 \times 1$
  $11 \div 2 = 5 \cdots 1$
  $5 \div 2 = 2 \cdots 1$
  $2 \div 2 = 1 \cdots 0$
  $1 \div 2 = 0 \cdots 1$

따라서, 자연수 $n$의 이진수는 자연수 n을 2로 나눈 몫이 0이 될 때까지 2로 나누고 그 나머지를 거꾸로 변환한 수이다.
따라서 이진수를 구하는 알고리즘을 파이썬으로 구현하면 다음과 같다.

def decimal_to_binary(decimal: int) -> str:
	binary = []
    while (decimal > 0):
    	binary.append(str(decimal % 2))
        decimal //= 2
    return "".join(reversed(binary))

decimal_to_binary(11)

>>> 1011

---

1.2. [백준 3460번] 이진수

위의 1.1. 이진법 알고리즘을 활용하여 다음과 같이 파이썬으로 문제를 풀이할 수 있다.

import sys

def print_binary(decimal: int) -> None:
	digits: int = 0
    while (decimal > 0):
    	if decimal % 2:
        	print(digits, end=" ")
            digits += 1
        decimal //= 2
    print(digits)

T = int(sys.stdin.readline())
for i in range(T):
	print_binary(int(sys.stdin.readline()))

---

1.3. Python 내장함수

사실 Python 내장함수에 진법 변환 함수가 있다.
bin(int): 10진수 → 2진수
oct(int): 10진수 → 8진수
hex(int): 10진수 → 16진수
int(str, n: int): n진수 → 10진수

bin(11)

>>> "0b1011"

oct(11)

>>> "0o13"

hex(11)

>>> "0xb"

int("b", 16)

>>> 11

---

2. 비트 연산자

비트 연산(bitwise operation): 한 개 혹은 두 개의 이진수에 대해 비트 단위로 적용되는 연산.
-Reference.Bitwise operation

2.1. Python 비트 연산자

Python의 비트 논리 연산자는 다음과 같다.
&: AND
|: OR
^: XOR
~: NOT

---

2.2. [백준 21396번] 이진수 더하기

위의 2.1. Python 비트 연산자를 활용하여 다음과 같이 파이썬으로 문제를 풀이할 수 있다.

import sys
from collections import Counter

T = int(sys.stdin.readline())

num = 0

for i in range(T):
	n, x = list(map(int, sys.stdin.readline().split()))
    v = Counter(list(map(int, sys.stdin.readline().split())))
    if x == 0:
    	for c in v.keys():
        	num += (v[c] * (v[c] - 1))
    else:
    	for c in v.keys():
        	num += (v[c] * v[x^c])
    print(num // 2)
    num = 0