S.E.B 0.0.9

클로드 섀넌 Claude Elwood Shannon(1916.4.30 ~ 2001.2.24)

미국의 수학자이자 전기공학자, 정보 이론의 아버지
그의 <A Mathematical Theory of Communication>논문은 정보 이론의 시초가 됨

정보 이론
최대한 많은 데이터를 매체에 저장하거나 채널을 통해 통신하기 위해 데이터를 정량화하는 응용 수학의 한 분야

• 전기회로 스위치의 on / off 를 이용한 스위칭 회로 연구를 하다가
  • true / false 의 2개 값으로 논리연산을 설명하는 부울대수 Boolean Algebra 를 적용하여 논리 게이트 Logic Gate를 만들어냄
• 논리 회로 Logic Circuit는 현대 모든 디지털 컴퓨터의 기본 개념이자 근간이 됨

8비트 = 1바이트, 1바이트는 0부터 255의 값을 지닐수 있음

부울연산자

부울 연산자 Boolean Operation (Q. 논리 연산자 Logical operator 와 같은것?)

• 논리식을 판단하여, 참(True)과 거짓(false)를 반환
• 기본 부울 연산자(and,or,not) → 결합/조합 → 보조 연산자(xor)
• NOT
  • A값이 True면 False
  • A값이 False면 True
    • not A
• AND
  • A 와 B 둘다 True 여야 True
    • A and B
• OR
  • A와 B중 하나라도 True 면 True
    • A or B
• XOR
  • 대표적인 보조 연산자
    • x = y = True
    • (x and not y) or (not x and y) = False

비트연산자

비트 연산자 Bitwise Operator

• 논리 연산자와 비슷하지만, 비트(bit) 단위로 논리 연산을 수행

• 비트 단위로 전체 비트를 좌우로 이동시킬때도 사용

  • 비트 AND 연산 , &

    • 대응 되는 비트가 모두 1이면 1을 반환

      

  • 비트 OR 연산, |

    • 대응 되는 비트중에서 하나라도 1이면 1을 반환

      

  • 비트 XOR 연산, ^

    • 대응되는 비트가 서로 다르면 1을 반환

      

  • 비트 NOT 연산, ~

    • 비트를 1이면 0으로, 0이면 1로 반전시킴

      

    • 비트연산자 NOT 인 ~ (틸드) 는 부울 변수에 적용하면 True 는 1로 간주되어 -2가 됨

    • 비트 연산자 NOT은 2의 보수에서 1을 뺀 값과 같기 때문

  • left shift 연산 , <<

    • 지정한 수만큼 비트를 전부 왼쪽으로 이동시킴

      

  • right shift 연산, >>

    • 부호를 유지하면서 지정한 수만큼 비트를 전부 오른쪽으로 이동시킴

    

    코딩교육 티씨피스쿨

파이썬의 진법 표현

• 파이썬에서 이진수(binary), 십진수(decimal), 16진수(hexadecimal)을 저장하고 표현하는 방법
• 십진수 → 이진수 표현
  • bin()
• 이진수 → 십진수 표현
  • int()
• 16진수 표현
  • hex()

>>>bin(87)
'0b1010111'

>>>int('0b1010111', 2)
87

#이진수임을 의미하는 접두사(Prefix) 0b는 생략 가능하다
>>>int('1010111', 2)
87

#bin()을 사용하여 변수에 값을 할당하면 문자형이 됨
>>> a = bin(87)
>>> a
'0b1010111'
>>> type(a)
<class 'str'>

#이진수를 문자열로 처리하지 않고 그대로 대입하면 십진수 숫자형이 됨
>>> b = 0b1010111
>>> b
87
>>> type(b)
<class 'int'>

#이진수를 대입한 변수 b는 십진수 숫자 87이 되고, 
#십진수 87과 ID도 동일하게 변함(내부적으로도 동일하게 처리됨)

>>>id(87)
4547371104
>>> b = 0b1010111
>>> b 
87
>>> id(b)
4547371104

#16진수 표현 접두사는 0x로 시작
#16진수는 bin()대신 hex()로 변환 가능
#문자열로 처리하지 않고 그대로 대입 가능
#ID도 동일하게 처리(내부적으로도 동일하게 처리됨)
>>>hex(87)
'0x57'
>>> c = 0x57
87
>>> id(c)
4547371104

비트조작예제

산술 연산Arithmetic Operation 을 활용한 비트 연산 예제

#덧셈
#자리수가 초과할때 다음 자리로 넘겨주는 십진수의 덧셈과 동일하게 처리
>>> bin(0b0110 + 0b0010)
'0b1000' 

#곱셈
#이진수의 곱셉은 십진수의 곱셈과 동일
#단 0은 모두 0이되고, 1은 기존의 값이 그대로 내려옴
>>> bin(0b0011 * 0b0101)
'0b1111' 

#우측시프팅
#우측2칸이 시프팅 되어 잘려나감
>>> bin(0b1101 >> 2)
'0b11'

#좌측시프팅
#지정한 수만큼인 2칸이 뒤로 추가
>>> bin(0b1101 << 2)
'0b110100'

>>> bin(0b0101 ^ ~0b1100) #0b1100 십진수로 변환시 12
'-0b1010' #-0b1010 십진수로 변환시 -10

#NOT x = -x - 1 
#x = 0b1100
#-12 -1 = -13
#-13을 2의 보수로 표현하면 111111...110011쯤 됨
#32비트 정수형일 경우 앞에 28비트는 모두 1
#앞에 값은 0b0101 이므로 이 값과 함께 XOR 연간을 한 결과는 111111...110110 이 됨
#이를 2의 보수로 표현하면 -10 이 됨

자릿수 제한 비트 연산

자릿수 제한을 통해 결과값 제어하기

• 0b1100 → 0b0011 이 되기 위해선 별도의 부가 작업이 필요
• 자릿수 만큼의 최댓값을 지닌 비트 마스크 MASK 생성후,
• 해당 값과 XOR을 통해 값을 생성

>>> bin(0b1100 ^ 0b1111)
'0b11'

>>> MASK = 0b1111
>>> bin(0b0101 ^ (0b1100 ^ MASK)
'0b110'

2의 보수

보수

• '두 수의 합이 진법의 밑수(N)가 되게 하는 수
  • 예) 10진수 4의 10의 보수는 6
  • 예) 10진수 2의 10의 보수는 8
• 컴퓨터에서 음의 정수를 표현하기 위해 고안된 방법 중 하나
  • 컴퓨터 내부에서 사칙연산을 할 때 덧셈을 담당하는 가산기Adder만 이용
    • 뺄셈은 덧셈으로 형식을 변환하여 계산해야 함
    • A - B 를 계산할때
    • B의 보수(-B)를 구한 다음
    • A + (-B)로 계산

1의 보수

• 각 자릿수의 값이 모두 1인 수에서 주어진 2진수를 뺀 값
  • 예) 2진수 1010의 1의 보수는 0101

2의 보수 Two's Complement

• 1의 보수에 1을 더한 값과 같음
• 2진수 1010에 대한 2의 보수를 구하려면?
  • 2진수 1010에 대한 1의보수 0101을 구한 다음 1을 더해 0110을 얻음
• 어떤 수를 커다란 2의 제곱수에서 빼서 얻은 이진수
• 2의 보수는 대부분의 산술연산에서 원래 숫자의 음수처럼 취급됨

2의 보수 숫자 포맷

• 2의 보수는 컴퓨터가 음수를 저장하기 위해 취하는 여러 방법 중 하나
• 4비트 레지스터 머신으로 가정한 숫자표현 예시
  • 4비트로 표현 가능한 범위는 0000 ~ 1111로 총 16개
  • 양수만 저장할시 0 ~ 15까지 16개를 저장가능
  • 음수도 저장할시 표현 가능 범위의 절반을 음수 몫으로 할당
    • 맨 앞 비트는 부호비트 (MSB,Most Significant Bit) 로 사용
      • 양수의 경우 0XXX
      • 음수의 경우 1XXX

https://img1.daumcdn.net/thumb/R800x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FKEgVL%2FbtqzuiU08Fj%2FX3dzGliEZmsIX2LV9l7kXK%2Fimg.jpg

2의 보수 숫자 포맷으로 시계방향으로 증가하는 형태로 값을 나열할 수 있다

• 2의 보수 숫자의 표현 범위는 $-2^{n-1}$에서 $2^{n-1}-1$

# 비트 마스크를 활용하면 4비트로 2의 보수를 표현하는 것과 동일한 값을 얻을 수 있음
>>> MASK = 0xF
>>> bin(1 & MASK)
'0b1'
>>> bin(7 & MASK)
'0b111'
>>> bin(-8 & MASK)
'0b1000'
>>> bin(-7 & MASK)
'0b1001'


4비트 2의 보수 숫자 포맷

파이썬에서 4비트로 2의 보수 표현하기

• 파이썬은 내부적(Cpython)으로 2의 보수를 임의 정밀도(Arbitrary-Precision)를 사용하여 구현
  • 임의정밀도 란?
    • 임의정밀도 정수형이란 무제한 자릿수를 제공하는 정수열을 말한다. 엄청나게 긴 정수를 입력받으면 그것을 잘라서 2^30 진법으로 만든다
    • 이 값을 별도로 계산하여 처리하는 방식인데 임의정밀도로 숫자를 처리하게 되면 계산 속도가 저하된다
• 부호는 별도 필드를 지님
• 비트 연산이 필요할 때만 2의 보수로 변환하는 작업을 수행
• 음수 표현할 때는 앞에 부호만 덧붙여 출력

# 파이썬에서는 2의 보수 값을 실제로 보여주지 않음
>>>bin(-5)
'-0b101'

#숫자를 4비트 혹은 32비트로 표현해도 비트 연산 결과는 동일하다
>>> 5 & -4
4

#4비트 2의 보수 표현 과 32비트 2의 보수 표현 비교
>>>bin(0b0101 & 0b1100) #4비트 2의 보수로 표현된  5 & -4 연산
'0b100' #4
#32비트 2의 보수로 표현된  5 & -4 연산
>>>bin(0b00000000000000000000000000000101 & 0b11111111111111111111111111111100)
'0b100' #4

#즉 결과는 같다

2의 보수 수학 연산

• 2의 보수 수학 연산은 가산 역 연산 Additive Inverse Operation 이라 할 수 있다.
• 양수 → 음수, 음수 → 양수로 바꾸는 작업을 말한다
• 비트연산자 NOT을 한 후에 1을 더하면 된다
  1. 비트 연산자 NOT 은 2의 보수에서 1을 뺀 것
  2. 2의 보수 수학 연산은 비트 연산자 NOT 에서 1을 더한것
• 0111 의 2의 보수 연산
  • 1000 + 1 = 1001
• 1001 의 비트 연산자 NOT
  • 0111 -1 = 0110
  • ~1001 로도 표현
• 7 → 0111
• 0111 의 2의 보수 연산 → 1001
• 1001 → -7
• 둘을 더하면 0이 됨
• 이진수로 계산할 경우 양수0111와 음수1001를 더하면 10000 이 되므로 오버플로가 발생함
• 하지만 4비트 연산이므로 초과한 자릿 수는 무시 → 0000, 즉 0이 됨

비트 연산자 NOT

• 비트연산자 NOT ⇒ ~(틸드) 연산자
• 기준 비트 내에서 1을 0으로, 0을 1로 바꿔준다
• 4비트라 가정시 → 0111 ⇒ 1000 이고
• 2의 보수 포맷에서는 0111 은 7이고 1000은 -8로
• NOT x = -x -1이 된다

>>>bin(0b0101 ^ ~0b1100) #0b0101 XOR NOT 0b1100
'-0b1010' #0b0110이 아닌 이유는 입력값이 4비트 포맷이 아님

#4비트 머신에서 0b1100이 음수 -4 여야 하는데 실제로는 양수 12로 가정
#오버플로가 발생한 상태 -> 8비트 혹은 더 큰 형태로 바꿔야 정확한 연산이 가능

>>>bin(0b00000101 ^ ~0b00001100) 
'-0b1010' # 위와 결과값이 같음을 알수 있다.

# ~0b00001100을 먼저 계산하고 다시 적용
>>>bin(0b00000101 ^ 0b11110011) #2번째 값을 2의 보수로 직접 만들고 NOT연산을 먼저 계산
'0b111110110'# 2의 보수이므로 해당 값은 -10 이다

#-0b1010도 -10이므로 동일하다

#16비트 , 32비트 에서의 결과도 같은 결과를 출력한다.