[파이썬 알고리즘] 19장 비트조작

부울 연산자

1. AND : 이항 연산자로, 둘 다 True인 경우에만 연산 결과가 True이다.
2. OR : 이항 연산자로, 둘 중 하나라도 True라면 연산 결과가 True이다.
3. NOT : 단항 연산자로, True이면 False로 False이면 True로 만든다.

 

비트 연산자 : bit단위로 논리연산을 수행할 때 사용하는 연산자

1. & : 동일한 위치의 bit가 모두 1인 경우에만 연산결과 1, 그 외의 경우 0
2. | : 동일한 위치의 bit 중 하나라도 1인 경우에 연산결과 1, 그 외의 경우 0
3. ~ : 그 위치의 bit가 1이면 0, 0이면 1
4. ^ : 동일한 위치의 bit가 다르다면 1, 동일하다면 0
5. << : left shift 연산자 (하위 비트는 0으로 채워진다)

6. >> : right shift 연산자 (MSB와 동일한 값으로 상위 비트를 채운다)

   1. 자바에서 >>> 연산자는 상위 비트를 그냥 0으로 채워버린다.

 

 

MASK

1. x ^ 1 = ~x
2. x ^ 0 = x

등 여러 속성을 이용하여 MASK bit를 만들기도 한다.

예를 들어, 1100 비트에 ~ 연산을 수행하면 어떤 결과가 예상되는가? 0011이 예상되는가?

그렇지 않다 🤔

 

만약 1byte의 저장공간에 1100 비트값이 저장되어 있다면, 상위 비트는 0000으로 채워져 있기 때문에 ~ 연산을 수행하면 11110011 이라는 결과값이 나오게 된다. 0011, 즉 00000011과는 다르다.

만약 1100에 대해 ~ 연산을 수행하여 0011 이라는 값을 얻고 싶다면, 1100 ^ 00001111 연산을 수행해주는 것이다.

이렇게 되면 00000011 이라는 값을 얻게 된다.

즉, 1100에 대응되는 위치에는 1111과 XOR 연산을, 그렇지 않은 경우에는 0000과 XOR 연산을 수행하여 상위 비트를 기존과 동일한 값으로 유지시키는 것이다. 여기서 사용한 00001111이 mask bit이다.

 

 

2의 보수

• 보수라는 개념은 음수를 표기하기 위해 등장한 개념이다.
• -1을 어떻게 표현할까?
  • 방법1) 가장 상위비트를 부호 비트로 두자
    • 1 = (00000001)_2
    • -1 = (10000001)_2
    • 이 때 1+(-1) = (00000001)_2 + (10000001)_2 = (10000010)_2 결과 해석하기 어렵다
  • 1. 보수를 사용하자
    • 방법2) 1의 보수 (~ bit operation을 적용한 결과)
      • 1 = (00000001)_2
      • -1 = (11111110)_2
      • 1 + (-1) = (11111111)_2 → 1을 더하면 0이 된다! 해석하기 보다 쉬워졌다.
    • 방법3) 2의 보수 ( 1의 보수에다 1을 더한 결과)
      • 1 = (00000001)_2
      • -1 = (11111110)_2 + (00000001)_2 = (11111111)_2
      • 1 + (-1) = (00000000)_2 → 결과 해석 편하다! (여기서 0이 된 이유는 overflow)
• 따라서 일반적으로 음수를 표현할 때 2의 보수를 사용한다 🙂