[JAVA] 2. 비트 연산자와 2의 보수

비트 연산자와 2의 보수

비트 연산자

• 비트 연산과 비트

  • 비트 연산은 이진수, 비트 문자열, 비트 배열에서 쓰이는 연산입니다. 비트 문자열 비트 배열은 비트를 저장하는 해당 데이터 구조를 일컫습니다. 비트의 위치는 오른쪽부터 시작해, 왼쪽으로 셉니다. 16비트에서, 이진수 0001은 가장 오른쪽 비트를 제외한 모든 위치에 0이 있습니다.

• 비트 연산의 특징

  • 비트 연산자는 정수형을 피연산자로 가지고, 각 자리 수에 대한 연산은 해당 자리에서만 영향을 미칩니다.

• 비트 연산/알고리즘의 장점

  1. 속도
     비트 연산은 프로세서에서 동작하는 까닭에, 산술 연산보다 더욱 빠릅니다.
  2. 공간 최적화
     비트 연산은 한 변수 안에 다양한 값을 저장할 수 있기에 메모리 제한이 있을 때 유용합니다.
  3. 비트 조작
     비트 연산자는 개별 비트를 조작할 수 있기에, 암호, 오류 탐지, 압축 분야에서 유용합니다.
  4. 코드 간결화
     비트 연산은 복잡한 조건문과 반복문을 줄일 수 있기에, 코드를 간결하게 만듭니다.
  5. 가독성 개선
     복잡한 논리를 한 연산으로 표현할 수 있기에, 코드를 이해하고 유지하기 더 쉽습니다.

• 비트 연산/알고리즘의 단점

  1. 복잡성
     이진수 표현과 비트 연산에 익숙하지 않은 사람들에게는, 이해하고 구현하기에 힘들 수도 있습니다.
  2. 이식성
     비트 연산은 다른 시스템으로는 잘 이식되지 않을 수 있습니다. 특히 기계 수준에서 이진 데이터를 처리하고 있을 경우에는 더욱 그렇습니다.
  3. 유지
     유지와 디버깅이 어렵습니다.
  4. 수행
     빠르고 유용할 수 있지만, 항상 최고의 선택은 아닙니다.

• 비트 연산자

  • 논리 연산자

    연산자	설명
    &	대응 되는 비트가 모두 1이면 1을 반환한다 (AND)
    |	대응 되는 비트 중에서 하나라도 1이면 1을 반환한다 (OR)
    ^	대응 되는 비트가 서로 다르면 1을 반환한다 (XOR)
    ~	비트가 1이면 0으로, 0이면 1로 반전시킨다 (NOT)

  • 이동 연산자

    연산자	설명
    <<	비트값을 주어진 숫자만큼 왼쪽으로 이동시킨 후, 빈자리는 0으로 채운다. (left shift)
    >>	비트값을 주어진 숫자만큼 오른쪽으로 이동시킨 후, 빈자리는 해당 정수의 최상의 부호 비트와 같은 값으로 채운다 (right shift)
    >>>	비트 값을 주어진 숫자만큼 오른쪽으로 이동시킨 후 빈 공간을 모두 0으로 채운다. (JAVA)

• 비트 연산자 진리표

  Fig 1. Bitwise Operator Truth Table

• 비트 연산자의 쓰임 추측

  • & (AND): 일치하는 값을 추출해내는 것에 쓸 수 있겠습니다.
  • | (OR): 해당하는 비트를 0으로 교체하거나 치환할 때 쓸 수 있겠습니다.
  • ^ (XOR): 한 피연산자 값에서 다른 피연산자 값으로 변했다면, 어떤 변화가 있었는지 알 수 있습니다.
  • ~ (NOT) : 2의 보수를 구하는 데 이용할 수 있습니다.

2의 보수 (Two's complement)

• 2의 보수란?

  • 2의 보수는 어떤 이진수가 있을 때, 그 이진수에서 한 자리 수 높고, 가장 높은 자리의 수가 1인, 2의 거듭제곱수를 만들기 위해 더하는 수입니다.
  • 1945년, 폰 노이만이 사용을 제안했습니다.

• 보수와 컴퓨터

  • 과거에, 컴퓨터 내부에서는 사칙연산을 할 때 덧셈을 담당하는 가산기(adder)를 이용했었다는 점과 관련됩니다. 즉, 뺄셈은 덧셈으로 형식을 변환해 사용해야 했습니다.
  • $A - B = A + (-B)$
  • 현재에는 컴퓨터가 음수를 저장하기 위해 자주 사용됩니다. N 비트의 크기를 가진다면, 경우의 수 절반은 0~양수에, 절반은 음수에 할당해서 사용합니다. (2의 보수)
  • $-2^{N-1} \quad \sim \quad 2^{N-1}-1$

• 2의 보수에서 양수와 음수

  • 이진수로 나타내는 경우, 맨 앞의 비트가 0이면 양수가, 1이면 음수입니다. 이를 부호 비트라 합니다. 혹은, MSB(most significant value)라고도 합니다.
    1. 양수 5의 표현
       $0101 = 0 \times (2^{-3}) + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0$
    2. 음수 -6의 표현
       $1010 = 1 \times (2^{-3}) + 0 \times 2^2 + 1 \times 2^1 + 0 \times 2^0$
       
  • 이제 양수 5, 0101의 2의 보수를 구해보겠습니다. 0101에 어떤 이진수를 더하면 한 자리 수 높고 MSB가 1인 2의 거듭제곱수가 되어야 합니다. 즉, 0101에 더했을 때 10000이 되는 수를 구해야 합니다.
  • 가장 쉽게 구하는 방법은, 10000에서 0101을 빼는 것입니다. 그렇다면 1011이라는 수가 나오는데요. 이는 0101에 ~ 연산을 한 뒤에 1을 더한 수입니다.

• 가장 작은 음수 (Most negative number)

  • 따라서, N비트에서 대부분의 이진수는 2의 보수로 자신의 부호를 바꾼 값을 갖습니다. 0은 0을 보수로 갖습니다. 그런데 가장 작은 음수는 자신을 2의 보수로 갖습니다.
  • 예시를 들어온 4비트에서, 가장 작은 음수는 1000 = -8 입니다. 2의 보수를 구하기 위해, ~ 연산을 한 뒤에 1을 더해보겠습니다. ~(1000) + 0001 = 0111 + 0001 = 1000 자신을 2의 보수라 갖게 됨을 알 수 있습니다.

• 1의 보수와 차이

  • 어떤 이진수에 대해 자릿수는 같고, 모든 비트가 1인 수를 만들기 위해 더하는 수가 1의 보수입니다. 1의 보수는 x라는 수에 대하여 ~x를 보수로 삼습니다.
  • 즉, $5= 0101$의 1의 보수는 $-5 = 1010$ 입니다.
  • 그렇다면 $0=0000$의 보수는 어떻게 될까요? 0의 1의 보수는 $1111$이 되며, $+0$과 $-0$이 따로 존재하는 문제가 생깁니다.
  • 2의 보수는 '오버플로우'에서 1의 보수가 갖는 문제 역시 해결합니다. 맨 앞 자리의 1은 버려지게 됩니다.

• C와 2의 보수, JAVA와 2의 보수

  • C에서는 자료형에 따라 signed / unsigned로 부호 유무가 결정되고, 산술 논리 장치(ALU)에서 자리 수가 하나 더 넘어갈 때 carry를 더해줘야 합니다.
  • JAVA에서는 변수에 따라 비트수가 결정되어 있고, 숫자 연산에서 자릿수가 벗어나면 C언어처럼 버리게 됩니다.

References

[Fig 1.]
https://www.geeksforgeeks.org/introduction-to-bitwise-algorithms-data-structures-and-algorithms-tutorial/

http://www.tcpschool.com/java/java_operator_bitwise
https://en.m.wikipedia.org/wiki/Two%27s_complement
https://ko.m.wikipedia.org/wiki/2의_보수