Bit 0 또는 1의 값을 가진다

Byte 8 비트이다(어떤 시스템에서는 16비트, 7비트로 사용하기도 함!) 0~255의 정수, 00~FF까지의 16진수를 표현 가능

Boolean 불린 연산을 말한다

• 집합 연산을 할 수 있다 00101011과 76543210을 대응시키면 {0,1,3,5} 교집합(and) 합집합(or) 여집합(not) 등
• 비트 연산을 할 수 있다 &&이 아닌 &, ||이 아닌 |, ^, ~를 사용해 정수 타입에 구현 가능
• 비트 시프트 연산
  • x<<y left shift x를 y칸 왼쪽으로; 왼쪽에 있던 비트는 삭제되고 오른쪽에는 0으로 채워진다
  • x>>y right shift 오른쪽에 있던 비트는 삭제, 왼쪽에는
    • unsigned면 0으로 채우고
    • signed면 부호에 따라서 0 또는 1에 맞춰 채운다.

Encoding Integers

• Unsigned: $B2U(X) = \sum\limits_{i=0}^{w-1} x_i \cdot 2^i$ UMin=0, UMax = $2^{n-1}$
• two’s complement (Signed) $B2T(X) = - x_{w-1} \cdot 2^{w-1}+ \sum\limits_{i=0}^{w-2} x_i \cdot 2^i$ 즉 맨 첫자리를 부호로 쓴다.
• -1은 1111…111로 쓰는 것을 주의

TMin = -2^(n-1) TMax = 2^(n-1) -1

• 1바이트씩 나눠서 2진수를 저장한다 ex) 15213 = 0011101101101101(2진수) → 00111011 01101101 → 0011 1011 0110 1101 → 3B 6D (2byte)

• Conversion

  • unsigned, 2’s complement는 일대일 대응이 된다(역함수가 존재한다)
  • 따라서 2의 보수로 표현된 정수를 부호 없는 정수로 표현할 수 있고 (앞쪽은 그대로, 뒤는 2^n 더하기)
  • 그 반대도 가능하며 그 과정에서 bit pattern이 바뀌지 않는다. (앞쪽은 그대로, 뒤는 2^n에서 빼기)
  • 코드에서 그냥 대입하고 cast 하면 된다.
  • signed와 unsigned를 비교 연산 하면 unsigned로 바뀌어서 비교!

  

Extension n비트 signed 정수를 n+k 비트로 확장하려면 sign bit를 왼쪽에 전부 똑같이 복사한다

사칙연산

• 덧셈

  • 2의 보수는 더하면 0을 만들기 위해서 고안되었다.

  

  • unsigned는 더하고 carry를 버린다. → 2^n보다 크면 2^n을 뺀다.
    • 아벨군
      • 덧셈에 닫혀 있음
      • 교환법칙
      • 결합법칙
      • 항등원(0)
      • 역원(2^n-x)

  

  • signed는 더하고 carry를 버린다. → overflow 일어나면 음수로 간다.
    • Unsigned의 덧셈과 동형 사상(isomorphic) TAdd(u,v) = U2T[UAdd{T2U(u), T2U(v)}]

• 곱셈

  • 최대 비트

    • unsigned: 2n
    • 2’s comp: 최소 2n-1, 최대 2n
      • 2n인 경우: (-2^n-1)^2 = 2^(2n-2)

  • unsigned에서 carry 버림 → x*y mod 2^n

    • 가환환을 이룬다
      • 닫혀 있음
      • 교환, 결합
      • 항등원 (1)
      • 분배법칙

  • signed에서 carry 버림 → 값이 달라진다

    

• 비트 시프트 곱셈

  • u<<k 하면 u * 2^k와 동일한 역할을 한다(signed, unsigned 전부 적용)
  • 따라서 u<<5 - u<<3 == u * 24 이런식으로 응용가능하다! 곱셈을 shift로 자동으로 변환해 준다.
  • logical shift

• 비트 시프트 나눗셈

  • u>>k 하면 u를 2^k로 나눈 몫이 나온다
  • 따라서 나누기도 비슷하게 응용할 수 있다!
  • 정수 나눗셈을 하면 몫이 나오는 이유(5/2==2)
  • 음수의 경우 ?

    • ceil(x / 2^k)를 원하므로

    • floor( x+2^(k-1) / 2^k)을 계산하면 된다. 실제 컴파일러도 아래와 같이 7을 더하고 계산한다.

    • arithmetic shift

      

정수와 메모리

• Big-Endian: 낮은 주소에 msb
• little-endian: 낮은 주소에 lsb x86은 little endian이다. *x86이란? 인텔의 intel 8086에 적용된 아키텍처로, 32비트 CPU를 관용적으로 뜻함

String

• Array of ASCII characters
• final character should be \0 (null)

예제

• 1: x가 아주 작으면 overflow 돼서 0보다 큼
• 4: ux=0이면 -1이 1로 돼서 틀릴 수 있음
• 5: x=0, y=TMin 이면 -y가 정의가 안됨, 2의 보수를 취해도 TMin이 되므로 반례
• 6: 아주 큰 x면 overflow로 음수
• 7: 마찬가지로 overflow로 음수
• 9: x=TMin이면 -x = TMin
• 10: x=0이면 (00000|00000)<<5 == 00000으로 안된다 0이 아니면 성립한다.
• 12: 음수의 right bit shift의 경우는 왼쪽이 1로 채워지기 때문에 의도하지 않은 값을 내놓는다.
• 13: x=0: 0 & (-1) == 0 ≠ 0 (모순)