[알고리즘 algorithm] 비트 연산과 비트 조작

출처:

<파이썬 알고리즘 인터뷰> 박상길 지음, 정진호 일러스트, 책만, 2020(https://www.onlybook.co.kr/entry/algorithm-interview)

- 부울 연산자

>>> True and False
False
>>> True or False
True
>>> not True
False

and, or, not은 기본 부울 연산자로, 이들을 조합하여 다른 보조 연산을 만들어 내는데, XOR 연산이 대표적인 보조 연산에 해당한다.

>>> x = y = True
>>> (x and not y) or (not x and y)
False

- 비트 연산자

>>> True & False # and
False

>>> True | False # or
True

>>> True ^ True # xor
False

>>> ~True # not
-2

비트 연산도 비슷하게 작용을 한다. 단 이진법 숫자를 각 자리 비트별로 쪼개서 연산을 시행한다.
예시 : bin(0b0010 & 0b0110)
&는 and 연산이므로 둘 다 1일 경우에만 1이다. 따라서 0010과 0110을 and 연산하면 0010이 된다.

비트연산자는 십진법으로 표기된 숫자에도 적용이 가능하다.
예를 들어 2^6을 출력하면 4가 나온다.
4인 이유는 2 = 0b0010, 6 = 0b0110이므로 XOR 연산을 적용하면 0b0100이 되기 때문이다.
(XOR연산에서는 값이 같으면 0, 값이 다르면 1이 된다.)

>>> 2^6
>>> bin( ~ 0b0010)
>>> bin(0b0010 & 0b0110)
>>> bin(0b0010 | 0b0110)
>>> bin(0b0010 ^ 0b0110)

4
-0b11
0b10
0b110
0b100


# not x = -x-1
>>> ~1
>>> ~8
>>> ~16

-2
-9
-17

주의할 점은  bin(~0b0010)을 출력하면 -0b11이 나온다. 이유는 다음과 같다.
0b0010에 not 연산을 적용하면 1111...1101이고 이는 1로 시작하므로 음수이다. 이 음수에 2의 보수 연산을 적용하면 0000...0011이 나온다. 2의 보수 연산을 모르면 나의 다른 글을 참고하면 된다.(아래 링크)
결론은 not x = -x-1로 출력이 된다.


- XOR 연산 활용
XOR 연산으로 재미난 것을 해볼 수 있다. XOR 연산은 교환법칙과 결합법칙이 성립한다.
0^x = x^0 = x 이고 x^x=0 이다. 또 x^y^x = y이다.

## XOR operation
## x^0 = 0^x = x
## x^x = 0
>>>  3^0
>>>  0^3
>>>  3^3
>>>  3^7^3
3
3
0
7

>>>  nums = [1,3,5,4,2,4,1,5,3]
>>>  sum=0
>>>  for num in nums:
>>>      sum ^= num
>>>  print(sum)
2

위의 경우처럼 nums 안에는 하나의 원소를 제외하고 모든 원소들이 모두 2개씩 존재한다. 오직 하나의 원소만 홀로 존재하는데 XOR연산으로 이 원소를 색출해낼 수 있다.
XOR 활용문제: leetcode.com/problems/hamming-distance/


* 2의 보수 연산 참고: yiyj1030.tistory.com/83?category=471598

2의 보수란?? 쉬운 설명으로 궁금증 해결.. (비트 연산)