AND연산

4장-2 비트 연산과 연산 순서

2019. 1. 14. 19:40

비트 연산, 시프트 연산, 연산 순서

2장 자료형에서 비트에 대한 얘기를 잠깐 하고 지나갔었죠?

컴퓨터는 모든 데이터를 0과 1로 저장합니다. 그걸 bit라고 하죠. 2진수로 볼 수 있습니다.
비트를 이용해 표현할 수 있는 수는 아래와 같습니다.

1비트로는 0, 1.
2비트로는 00, 01, 10, 11.
3비트로는 000, 001, 010, 011, 100, 101, 110, 111.

int는 4bytes(32bits)로 표현되는 정수입니다.

그런데 이런 데이터를 산술 연산이 아닌 bit끼리 비교하는 방법이 있습니다. 그걸 비트 연산이라고 합니다.
뭐랄까, 메모리의 데이터를 그대로 비교한다는 느낌일까요?

그래서 비트 연산은 사칙 연산이 아닌 다른 연산을 할 때 주로 사용합니다. AND, OR, XOR, NOT, 그리고 시프트 연산이 있습니다.

AND, OR, XOR, NOT 연산

비트 연산에 적용하기 전에 이 연산자들이 어떤 연산을 하는지 먼저 알아보도록 하겠습니다.

보통 비트 연산에서는 0이 거짓, 1이 참이라고 생각하면 편하게 계산할 수 있습니다.

AND(&)연산은 두 비트가 모두 1일 경우에 결과값이 1이 됩니다. a & bab 모두 참인지 물어보는 연산이라고 생각하면 됩니다.

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

OR(|)연산은 두 비트 중 하나라도 1일 경우에 결과값이 1이 됩니다. a | bab 둘 중 하나라도 참인지 물어보는 연산입니다.

0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

XOR(^)연산은 두 비트가 같으면 결과값이 1이 됩니다.

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

NOT(~)연산은 좀 다릅니다. 두 데이터를 비교하는 게 아닌, 하나의 데이터를 반전하는 연산입니다.

0 = 0
1 = 1
~0 = 1
~1 = 0

컴퓨터에서 비트 연산

변수는 1비트로 이루어져 있지 않습니다. 참과 거짓만을 저장하는 boolean을 제외하고 가장 작은 자료형이 char입니다. 1byte 자료형이고, 비트로는 8bits입니다.

그렇다면 여러 자리의 bits는 어떻게 연산할까요? 이 글의 초반에 메모리의 데이터를 그대로 비교하는 느낌이라고 했던 것 기억하시나요? 비트 연산을 할 때, 컴퓨터는 메모리의 값이 어떤 의미를 가지고 있는지는 상관하지 않습니다. 단지 하나의 bit 끼리만 비교하는 거지요.

여기, 1 byte크기의 데이터가 두 개 있습니다.

각각 a=0010 0101(정수 37), b=1000 0110(정수 -122) 라고 해보지요. 1 byte는 8 bits데이터입니다. 8 bits 크기의 데이터를 하나의 bit 끼리 비교한다면 각 자리별로 총 8번 'bit 연산'을 수행하면 됩니다.

이제 두 데이터 a와 b를 AND, OR, XOR, NOT연산을 해보겠습니다.

AND 연산

a = 0010 0101(37)
&
b = 1000 0110(-122)

A = 0000 0100(4)

OR 연산

a = 0010 0101(37)
|
b = 1000 0110(-122)

A = 1010 0111(-89)

XOR 연산

a = 0010 0101(37)
^
b = 1000 0110(-122)

A = 1010 0011(-93)

NOT 연산

a = 0010 0101(37)
~a = 1101 1010(-38)

b = 1000 0110(-122)
~b = 0111 1001(121)

NOT연산은 정수값을 보니 어떤 의미인지 좀 보이지 않나요?ㅎㅎ

Shift(시프트 연산)

비트 연산은 메모리의 데이터가 의미하는 바에 상관 없이 비트 끼리만 연산하는 거라고 했습니다.

그렇다면 그 비트를 왼쪽이나 오른쪽으로 옮기는 연산도 있지 않을까요?

그것을 Shift 연산이라고 합니다.

#include<stdio.h>
void main(){
    int i = 64;
    i = i << 1;

    printf("%d", i);

    i = i >> 1;

    printf("%d", i);
    return ;  
}

와 같은 형식으로 쓰입니다.

그런데 이 연산의 결과가 재미있습니다.

값이 64인 i를 왼쪽으로 한 번 시프트하면 i는 원래의 두 배인 128이 됩니다. 두 번 시프트 하면 256이 되죠. 반대로 오른쪽으로 시프트하면 128, 그리고 64가 됩니다.

한 번 왼쪽으로 시프트하면 값이 두 배가 됩니다. 오른쪽으로 한번 시프트 연산을 하면 값이 반이 됩니다. 어떻게 이런 결과가 나올까요? 바로 이진법의 원리 때문입니다.

이진법으로 숫자를 써보면 아래와 같습니다.

1 = 0000 0001
2 = 0000 0010
4 = 0000 0100
8 = 0000 1000
32 = 0010 0000
128 = 1000 0000(unsigned char)
-128 = 1000 0000(signed char)

-128인 이유는 '2의 보수' 개념을 사용하기 때문입니다. 2장-2글을 참고하세요

앗, 그러면 두 배를 곱할 때는 i = i * 2; 보다는 i = i << 1;이 빠르지 않을까요? 논리적으로는 맞습니다. 그런데 굳이 그럴 필요는 없습니다. 우리는 컴퓨터에 직접 명령하는 게 아니라, 명령을 적으면 컴파일러가 적절히 최적화 하기 때문이죠.

마지막을 보면 << 연산을 하면 64가 -128이 됩니다. 변수의 크기, 부호의 여부에 따라 음수가 나옵니다. 예상하던 결과와는 다른 값이 나옵니다. 그런데 곱셈 연산도 마찬가지입니다. 컴파일러는 부호가 있는(signed) 변수인 것을 알고 있지만 똑같이 -128이 되죠.

-128을 << 연산을 하면 어떻게 될까요? 비트로 보자면 1 0000 0000입니다. 하지만 8 bits만 할당 된 변수에서는 가장 앞의 1은 버려지고 결과는 0000 0000(0)이 됩니다. 곱셈 연산을 하더라도, 컴파일러는 char 자료형이 8 bits 변수인 것을 알지만 같은 결과가 나타납니다. 똑같이 예상하던 결과와 달른 값이 나오죠.

결국 컴파일러는 같은 연산으로 처리한다는 것을 어림잡아 볼 수 있을 것 같습니다.

3장에서 나누기 연산에 사용되는 두 변수가 모두 정수형이면 정수형으로 결과가 나온다고 했던 것 혹시 기억하시나요?

오른쪽 시프트 연산의 결과는 정수형의 나눗셈 연산과 결과가 같습니다.

변수 0101 0101(85)가 있습니다.

Rsh 1 회 : 0010 1010(42)
Rsh 2 회 : 0001 0101(21)
Rsh 4 회 : 0000 0101(5)
Rsh 6 회 : 0000 0001(1)

오른쪽 시프트를 할 때, 가장 왼쪽의 bit가 다음 bit에 복제됩니다. 그래서 부호를 나타내는 bit는 유지됩니다. 그렇기 때문에 음수에서도 나눗셈의 결과를 볼 수 있습니다.
하지만 음수에 대해서는 시프트 연산과 나눗셈이 다릅니다. 비트연산은 소숫점 자리를 버린다고 했죠? -12.1보다 작은 가장 큰 자연수는 -13입니다. 일반적으로 생각하는 버림과는 조금 다르죠.

음수인 1010 1010(-86)으로 비교해볼까요?

횟수 Bit 연산 정수 연산
1 1010 1010(-86) -86
2 1101 0101(-43) -43
3 1110 1010(-22) -21
4 1111 0101(-11) -10
6 1111 1101(-3) -2
8 1111 1111(-1) 0

비트 연산에서는 소수점 자리를 버립니다. 음수가 더 작은 수가 맞기 때문에 단순한 시프트 연산에서는 맞는 결과이죠. 정수의 나눗셈 연산에서는 사람에게 자연스럽게 소숫점 자리를 버립니다.

1111 1111>> 연산을 아무리 반복해도 -1입니다. 왜냐하면 -1을 2로 나누면 -0.5인데, 이걸 내림연산 하면 -1이 되기 때문입니다.

정수의 나눗셈에서는 -1을 2로 나누면 -0.5이고, 소수점 자리를 버리면 -0 = 0 이 되는 것입니다.

왼쪽 시프트를 얘기하면서 곱셈 대신 시프트를 사용하면 더 빠르다고 말했습니다. 하지만 컴파일러가 최적화를 하기 때문에 시프트 연산을 사용할 필요는 없다고 했죠.
그런데 최적화의 문제만이 아니라 연산의 결과가 달라질 수도 있습니다. 그러니 오류를 무릅쓰고 시프트 연산을 사용할 필요는 없다는 결론을 내릴 수 있습니다.

연산자 순서

산술 연산과 비트 연산들을 소개하면서 연산 순서에 관한 얘기를 몇 번 했습니다.

일단 순서와 관련한 표를 볼까요?

순서 연산자 설명 Associativity (연산자 내 순서)
1 ++a --a Suffix/postfix 증감 연산자 Left-to-right
() Functional forms
[] 배열 지정 연산자
. 구조체와 공용체 접근자
-> 포인터를 통한 구조체와 공용체 접근자
(type) {list} Compound literal
2 a++ a-- Prefix 증감연산자 Right-to-left
+a``-a 단항 연산자 : a를 음수로 만들거나 양수로 만드는 연산자
!``~ 비트연산 NOT, 논리연산 NOT
(type) 형 변환
* Indirection (dereference) (참조)
& 변수의 주소를 가리킴
sizeof Size-of(크기 확인용 연산자)
_Alignof Alignment requirement
3 * / % 곱셈, 나눗셈, 나머지 Left-to-right
4 + - 덧셈, 뺄셈
5 << >> 왼쪽 시프트, 오른쪽 시프트
6 < <= 비교 연산자
> >= 비교 연산자
7 == != 비교 연산자
8 & Bitwise(비트 연산) AND
9 ^ Bitwise XOR (exclusive or)
10 | Bitwise OR (inclusive or)
11 && Logical AND
12 | | Logical OR
13 ? : Ternary conditional(3항 조건 연산자) Right-to-Left
14 = 대입 연산
+= -= 복합 산술 연산
*= /= %= 복합 산술 연산
<<= >>= 복합 비트 연산
&= ^= |= 복합 비트 연산
15 , Comma Left-to-right

출처 : cppreference.com

너무 많죠? 너무 많아요... 하지만 뒤쪽을 배우다 보면 금방 외웁니다. 아니, 외울 필요도 없습니다. 너무 당연한 순서이기 때문이죠.

예시를 하나 볼까요?

#include <stdio.h>
void main(){
    int a = -43, b = ~(6 - 5) - 1 - 3;
}

와우 정말 쓸 데 없는 프로그램입니다.

가 아니고...

int a = -43, b = ~(6 - 5) - 1 - 3;안에 있는 연산자들을 위 표에서 찾아보세요.
Functional Forms (), 대입연산자 =, 단항연산자 -, 콤마 , , 비트 연산 ~, 산술 연산자 -까지 보입니다.
이 연산자들이 어떤 의미일지 한 번 보세요. 그리고 순서를 한 번 보세요. 꽤나 상식적인 부분이 많습니다.

이 중에 첫번째인 것은 ()입니다. 순서에 따라 연산하면 int a = -43, b = ~1 - 1 - 3; 이 되겠네요.

두번째 연산자는 단항 연산자 -~입니다. 그러면 int a = -43, b = -2 - 1 - 3; 가 됩니다. 단항 연산자는 딱히 표시할 방법이 없습니다. 0010 10111101 0101되었다고 보면 될 것 같습니다.

세번째 연산자는 산술 연산자 -입니다. 그런데 -는 연산자 내에서도 순서가 있죠. 처음에는 int a = -43, b = - 3 - 3; 이 되고, int a = -43, b = - 6; 이 됩니다.

네번째 연산자는 =입니다. 각각의 값을 a와 b에 대입합니다. ,의 순위가 가장 낮기 때문에 a와 b를 한 줄에서 선언해도 서로 영향을 주지 않습니다. 또한 ,는 왼쪽 부터 연산을 하기 때문에 a에 먼저 -43을 대입하고 b-6을 대입합니다.

요약

  • AND, OR, XOR ,NOT연산을 이해할 수 있다.
  • <<연산과 >>연산을 이해할 수 있다.
  • 곱셈과 나눗셈, 시프트 연산의 차이를 알 수 있다.
  • 연산의 순서를 이해하고 외울 수 있다.

'컴퓨터공학 > C' 카테고리의 다른 글

2장-2 변수의 크기와 오버플로우, 언더플로우  (0) 2019.05.05
4장-1 산술 연산자  (0) 2019.01.14
3장 printf scanf 함수  (0) 2019.01.10
2장-1 자료형  (0) 2019.01.10
1장-1 Hello World  (0) 2018.12.16

+ Recent posts