---
# System prepended metadata

title: 컴퓨터의 숫자 표현
tags: [과외(하희영)]

---

# 컴퓨터의 숫자 표현

## 이진법

**0과 1 두 개의 숫자로만 사용해서 수를 나타내는 진법**

- 이진법은 컴퓨터 세계에서 널리 사용되는 숫자 체계다
    - 현재 우리가 주로 사용하고 있는건 10진법이다
- 컴퓨터는 전기적 신호를 사용하여 정보를 처리하고 저장하는데, 이진법은 이러한 전기적 신호를 쉽게 표현할 수 있기 때문에 컴퓨터에서 사용되고 있다.
    - 0은 '꺼진' 상태를, 1은 '켜진' 상태를 나타낼 수 있다.
- 이진법의 기초를 이해하면 컴퓨터 과학에서 중요한 개념들을 배울 때 도움이 된다.
    - 예를 들어, 이진법은 컴퓨터 메모리와 데이터 표현, 비트 연산, 프로그래밍 등 다양한 분야에서 활용된다.
![](https://i.imgur.com/lWu9PO6.png)

## 자바에서의 진수 표기법 (2진법, 8진법, 16진법)

![](https://i.imgur.com/77MCb0V.png)

- 2진법 : 숫자 앞에 `0b` 또는 `0B` 접두어를 붙인다.
  - `int binaryNumber = 0b1010; // 10진법으로 '10'`
- 8진법 : 숫자 앞에 `0` 접두어를 붙인다.
  - `int octalNumber = 012; // 10진법으로 '10'`
- 16진법 : 숫자 앞에 `0x` 또는 `0X` 접두어를 붙인다.
  - `int hexNumber = 0xA; // 10진법으로 '10'`
- 일반적으로 컴퓨터 분야에서 16진법을 사용하는 경우가 많은데 그 이유는 다음과 같다
  - **가독성**: 16진법은 긴 이진수의 가독성을 향상시킨다. 이진수는 길고 혼란스러울 수 있지만, 16진수를 사용하면 비교적 짧고 명확한 표현이 가능하다.
  - 간결성: 16진법은 이진법보다 숫자를 표현하는 데 더 간결한 방법을 제공한다. 4비트 이진수를 하나의 16진수로 표현할 수 있으므로, 큰 이진수를 쉽게 읽고 쓸 수 있다. 예를 들어, 8비트 이진수 1011 1100은 16진수 BC로 간단하게 나타낼 수 있다.
  - 디버깅 및 메모리 주소: 프로그래밍에서 16진법은 디버깅을 쉽게 만들어주며, 메모리 주소를 표현하는 데 적합하다. 메모리 주소와 바이너리 데이터를 짧게 표현할 수 있어, 프로그래머가 이해하기 쉽다.


> 자바에서는 각 진법의 숫자를 10진법으로 변환하거나, 다른 진법의 문자열로 변환할 때 도와주는 메서드를 제공한다.
> ``` java
> int num = 42;
> 
> // 2진수로 변환
> String binaryString = Integer.toBinaryString(num); // Output: "101010"
> 
> // 8진수로 변환
> String octalString = Integer.toOctalString(num); // Output: "52"
> 
> // 16진수로 변환
> String hexString = Integer.toHexString(num); // Output: "2a"
> 
> ```
> ---
> ``` java
> String binaryString = "101010";
> String octalString = "52";
> String hexString = "2a";
> 
> int binaryNum = Integer.parseInt(binaryString, 2); // Output: 42
> int octalNum = Integer.parseInt(octalString, 8); // Output: 42
> int hexNum = Integer.parseInt(hexString, 16); // Output: 42
> ```

---

## 보수

- 어떤 집합 내에서 두 개의 원소를 더했을 때, 특정 기준 값이 되게 하는 원소들의 관계를 의미

**10의 보수 (10's complement)**

- 10진수 체계에서 사용되는 보수.
- 어떤 수와 그 수의 10의 보수를 더하면 10의 배수가 된다.
    - 예를 들어, 7의 10의 보수는 3이다. 왜냐하면 7 + 3 = 10이기 때문.

**2의 보수 (2's complement)**

- 2진수 체계에서 사용되는 보수.
- 어떤 이진수와 그 수의 2의 보수를 더하면 2의 배수(예: 10000, 1000 등)가 된다.
- 2의 보수를 구하는 방법은 해당 이진수의 비트를 모두 반전시킨 후 1을 더하는 것.
    - 예를 들어, 이진수 1101의 2의 보수는 0011다. 왜냐하면 1101의 비트를 모두 반전시키면 0010이 되고, 여기에 1을 더하면 0011이 되기 때문.



## 정수 표현

**부호 없는 정수(unsigned integer)**

- 부호 없는 정수는 양수와 0만 표현할 수 있으며, 모든 비트가 값에 사용된다. 예를 들어 8비트 부호 없는 정수는 다음과 같이 표현된다.
```
00000000 = 0
00000001 = 1
00000010 = 2
00000011 = 3
...
11111110 = 254
11111111 = 255
```

**부호 있는 정수(signed integer)**

- 부호 있는 정수는 양수, 음수, 그리고 0을 표현할 수 있다.
- 가장 널리 사용되는 방식은 2의 보수(two's complement) 표현이다.
    - 이 방식에서는 가장 왼쪽에 있는 비트가 부호 비트로 사용되며, 0은 양수, 1은 음수를 나타낸다. 나머지 비트는 값을 표현하는데 사용된다.

```
00000000 = 0
00000001 = 1
00000010 = 2
...
01111111 = 127
10000000 = -128
10000001 = -127
...
11111110 = -2
11111111 = -1
```

### `unsgined` 자료형

- 부호가 없는 자료형을 `unsigned` 자료형이라고 한다.
    - 앙수값만 필요한 상황에서 주로 사용된다.
- 자바에서는 의도적으로 `unsgined` 자료형을 지원하지 않는다.

#### `unsigned` 자료형을 지원하지 않는 이유

- 간결함: 자바 언어는 단순하고 명확한 구문과 개념을 가지고 있으며, 이를 위해 불필요한 복잡성을 제거하려고 하는데, `unsigned` 정수 자료형을 포함하면 언어의 복잡성이 증가하고, 프로그래머들이 다양한 경우에 대해 고려해야 한다.
- 프로그래밍 오류 줄이기: 프로그래머가 `signed` (부호 있는) 정수와 `unsigned` 정수를 혼용할 경우, 예기치 않은 결과를 초래할 수 있는 문제가 발생할 수 있다. 이러한 오류를 방지하기 위해 자바는 `unsigned` 정수를 지원하지 않는다.
- 표준화 및 이식성: 자바는 플랫폼 독립적인 언어로 설계되었기 때문에, 다양한 플랫폼에서 동일한 결과를 얻으려는 목적을 가지고 있다. 일부 플랫폼에서는 `unsigned` 정수를 다르게 처리할 수 있으므로, 이식성에 영향을 미칠 수 있다.

#### `unsigned` 자료형을 지원하지 않아서 발생하는 문제

- 자바에서 큰 양수를 처리하는데 어려움이 발생할 수 있다.
    - 예를 들어, 32비트 정수에서 `signed` int는 최대 2,147,483,647까지 표현할 수 있지만, `unsigned` int의 경우 4,294,967,295까지 표현할 수 있다.
- 외부 데이터와 상호 작용 시 추가적인 처리 비용이 발생하며, 오류가 발생할 가능성도 높아진다.
    - 다른 언어나 프로토콜에서 `unsigned` 정수를 사용하는 경우, 자바로 데이터를 가져오거나 전송할 때 변환 작업이 필요하기 때문.
- 비트 연산 시 추가적인 검사와 변환 과정이 필요하며, 성능 저하와 코드 복잡성 증가를 초래할 수 있다.
    - 비트 연산에서 `unsigned` 정수를 사용할 때, 부호 있는 정수로 변환해야 하는 경우 결과가 부정확해질 수 있다.

> **일반적으로 `unsigned` 자료형을 사용하는 경우**
>
> - 파일 크기: 파일의 크기는 항상 양수
> - 네트워크 패킷: IP 주소, 포트 번호 및 패킷 길이와 같은 네트워크 관련 값은 항상 양수
> - 암호화 및 해싱: 암호화 및 해싱 알고리즘은 종종 큰 양수 값을 사용
> - 이미지 처리: 이미지의 픽셀 값은 보통 0부터 255 사이의 값을 사용
> - 그래픽 및 게임 개발: 그래픽 및 게임 개발에서는 종종 정점 인덱스나 렌더링 순서와 같은 양수 값만 필요한 데이터를 사용


---

## 컴퓨터의 음수 표현

- 컴퓨터는 `0`과 `1` 이진수만 이해할 수 있기 때문에, `+`, `-` 같은 부호를 의미하는 음수 표현에도 `0`, `1`로 표현한다.
- 컴퓨터는 부호 표현외에도 덧셈, 뺄셈의 계산을 용이하게 하기 위해 `2의 보수`를 사용하고 있다.
    - `2의 보수`를 사용하면 덧셈 연산에서 처리를 더 단순화시키게 되며 가장 단순하면서 효율적
     ![](https://i.imgur.com/u7oJn03.png)

### 보수

- 정의 : 어떤 수나 집합에 대해, 그 수나 집합의 보수(complement)는 그것과 상호 배타적이며 전체를 이루는 다른 수나 집합을 의미
    - 예를 들어, 어떤 집합 A가 있다면, 그 집합의 보수는 A에 속하지 않는 모든 원소들의 집합을 말한다. 이때 전체 집합은 A와 그 보수의 합집합이 된다.
- 일반적으로는 덧셈에 대한 역연산을 의미한다

---

## 실수 표현

- 컴퓨터에서는 2진수 체계를 기반으로 데이터를 처리하기 때문에, 실수도 2진수 메모리 비트로 표현해야한다. 컴퓨터에서는 실수를 표현할 때 `고정 소수점 방식`과 `부동 소수점 방식`을 사용한다.

### 고정 소수점(fixed point) 방식
![](https://i.imgur.com/CGPa33C.png)

- 직관적으로 메모리에 실수 표현을 할 수 있다는 장점이 있지만, **표현 가능한 범위가 매우 적다**는 단점과 **낭비되는 공간이 많이 생긴다**는 단점이 존재한다.
- ![](https://i.imgur.com/kWsMazR.png)
- `7.75` 라는 실수가 있을 경우, 고작 `0.75` 라는 작은 숫자를 표현하기 위해 16비트의 소수부를 모두 사용한다.
  - 공간 낭비를 줄이고 효율적으로 실수 메모리를 표현하기 위해 컴퓨터는 **부동 소수점 방식**을 사용한다.



---

### 부동 소수점(floating point) 방식

![](https://i.imgur.com/n9jXgWO.png)
- 부동(不動)이 아니라 부동(浮動)이다.
    - '움직이지 않는다'가 아니라 '떠서 움직인다'라는 뜻.
- 부동소수점은 실수를 컴퓨터에서 근사적으로 표현하는 방식
- 부동소수점은 부호 비트, 지수 부분, 가수 부분으로 이루어지며, 지수 부분의 bias 값이 사용된다.
    -  bias 값은 부동소수점 표현 방식에서 지수 부분을 부호화하기 위한 상수이며, 이 값을 더해 실제 지수 값을 계산한다.
        - 32비트 부동소수점의 경우, bias 값은 127이며, 64비트 부동소수점의 경우, bias 값은 1023이다.
- ![](https://i.imgur.com/UdqNgod.png)
  - 직관적이지 않아 오히려 번거롭게 보일수도 있곘지만, 이런식으로 실수를 표현하는 이유는 큰 범위의 값을 표현하기 위해서다
- 현재 사용되고 있는 부동 소수점 방식은 대부분 IEEE 754 표준을 따르고 있다. 그리고 자바도 이 표준을 따른다.
    - http://www.ktword.co.kr/test/view/view.php?m_temp1=4886

> 


**실수를 부동소수점 방식으로 표현하는 방법**

1. 실수 값을 이진수로 변환한다.
2. 이진수로 변환한 값을 가수 부분으로 정규화(normalization)한다. 이때, 가수 부분은 1.xxxxx 형태로 되어야 하며, 첫 번째 자리가 1이어야 한다.
3. 가수 부분의 값을 고정된 비트 수로 반올림하고 저장한다. 이때, 지수 부분을 통해 소수점의 위치를 조절할 수 있다. 부동 소수점 방식에서는 보통 32비트 또는 64비트의 메모리 공간을 사용한다.
4. 부호 비트, 지수 부분, 가수 부분을 결합하여 하나의 부동 소수점 값을 생성한다. 이때, 부호 비트는 0 또는 1로 표현하며, 지수 부분과 가수 부분은 2진수로 표현한다.
---

**32bit 부동소수점 포현 (float)**
![](https://i.imgur.com/umYEVFn.png)

---
**64bit 부동소수점 표현 (double)**
![](https://i.imgur.com/cUjELDn.png)

---

> 예시 `-118.625`(십진법)을 IEEE 754 (32비트 단정밀도)로 표현해 보자.
>
> - `-118.625`의 절댓값을 이진법으로 나타내면 `1110110.101`이 된다.
> - 소수점을 왼쪽으로 이동시켜, 왼쪽에는 1만 남게 만든다. 예를 들면 `1110110.101=1.110110101×2⁶` 과 같다. 이것을 정규화된 부동소수점 수라고 한다.
> - 가수부는 소수점의 오른쪽 부분으로, 부족한 비트 수 부분만큼 0으로 채워 23비트로 만든다. 결과는 `11011010100000000000000`이 된다.
> - 지수는 6이므로, Bias를 더해야 한다. 32비트 IEEE 754 형식에서는 Bias는 127이므로 6+127 = 133이 된다. 이진법으로 변환하면 `10000101`이 된다.
> - 음수이므로, 부호부는 1이 된다.
> - ![](https://i.imgur.com/Pd0HEdP.png)

---

## 컴퓨터에서의 실수 표현과 연산에서 발생하는 오차

**컴퓨터는 실수 표현 시 오차가 발생할 수 있다**

- 소수점을 사용하는 실수는 10진수 체계를 기반으로 두고 있지만, 컴퓨터는 **2진수 체계**를 사용한다.
- 실생활에서 사용하는 간단한 숫자라도, 컴퓨터 세계에선 **순환소수가 될 수 있다**
- 컴퓨터는 유한한 비트만 사용하여 숫자를 표현하기 때문에 **순환소수는 정확하게 표현할 수 없다**.
    - 이 경우 컴퓨터는 최대한의 **근사값을 사용**한다

즉, 컴퓨터는 실수를 정확하게 표현하지 못하고 근사값을 사용한다. 따라서 실수 연산을 할 경우 오차가 발생할 수 있다.

### In computer `0.1 + 0.1 + 0.1 ≠ 0.3` 

``` java
double sum;

sum = 0.1;
System.out.println(0.1 == sum);

sum = 0.1 + 0.1;
System.out.println(0.2 == sum);

sum = 0.1 + 0.1 + 0.1;
System.out.println(0.3 == sum);

// <RESULT>
// true
// true
// false
```

- 실수는 IEEE 754 표준에 따라 표현되고, 이 표준에서 `0.1`은 근사값으로 표현되며, 약간의 오차가 있을 수 있다.
    - `0.1`이라는 숫자는 이진수로 표현될 때 순환소수가 되어버린다
        - `0.00011001100110011...`
- 오차가 있는 실수를 대상으로 연산을 수행하면 오차가 누적된다.
    - `0.1` 을 세번 더할 경우 이 누적값이 결과값에 유의미한 영향을 미치는 수준에 이르러서 `0.1 + 0.1 + 0.1 ≠ 0.3`가 되어버린다.

### 실수 오차를 줄이기 위한 정수 변환 전략

**금융, 과학, 공학 등 정확한 수치가 필요한 분야에서 실수표현식을 그대로 사용할 경우 문제가 발생하기에 가능하면 정수로 표현해서 사용하는게 권장된다.**
- 1.1 달러 → 1달러 10센트
- 3.3m → 3m 30cm
- 0.1 sec → 100ms

---

## 과제1 : Integer 이진 트리 구현

목표: 자바로 이진 트리(Binary Tree)를 구현한다.

**요구사항**

- `Integer` 데이터 타입을 저장할 수 있는 이진 트리(`IntegerBinaryTree`) 클래스를 구현한다.
- `IntegerBinaryTree` 클래스는 다음의 메소드를 포함해야 한다
  - `public void insert(int data)`: 트리에 새로운 노드를 삽입한다.
  - `public boolean contains(int data)`: 트리에서 지정된 데이터를 가진 노드가 있는지 확인한다.
  - `public void delete(int data)`: 트리에서 지정된 데이터를 가진 노드를 삭제한다.
  - `public void preOrderTraversal()`: 전위 순회(pre-order traversal)를 사용하여 트리의 모든 노드를 출력한다.
  - `public void inOrderTraversal()`: 중위 순회(in-order traversal)를 사용하여 트리의 모든 노드를 출력한다.
  - `public void postOrderTraversal()`: 후위 순회(post-order traversal)를 사용하여 트리의 모든 노드를 출력한다.

---

## 과제 1 답안 예시

``` java
class Node {
    int data;
    Node left, right;

    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}

public class IntegerBinaryTree {
    Node root;

    public void insert(int data) {
        root = insertRec(root, data);
    }

    private Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }

        if (data < root.data) {
            root.left = insertRec(root.left, data);
        } else if (data > root.data) {
            root.right = insertRec(root.right, data);
        }

        return root;
    }

    public boolean contains(int data) {
        return containsRec(root, data);
    }

    private boolean containsRec(Node root, int data) {
        if (root == null) {
            return false;
        }

        if (root.data == data) {
            return true;
        }

        return data < root.data ? containsRec(root.left, data) : containsRec(root.right, data);
    }

    public void delete(int data) {
        root = deleteRec(root, data);
    }

    private Node deleteRec(Node root, int data) {
        if (root == null) {
            return root;
        }

        if (data < root.data) {
            root.left = deleteRec(root.left, data);
        } else if (data > root.data) {
            root.right = deleteRec(root.right, data);
        } else {
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            root.data = minValue(root.right);
            root.right = deleteRec(root.right, root.data);
        }

        return root;
    }

    private int minValue(Node root) {
        int minValue = root.data;
        while (root.left != null) {
            minValue = root.left.data;
            root = root.left;
        }
        return minValue;
    }

    public void preOrderTraversal() {
        preOrderTraversalRec(root);
        System.out.println();
    }

    private void preOrderTraversalRec(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrderTraversalRec(root.left);
            preOrderTraversalRec(root.right);
        }
    }

    public void inOrderTraversal() {
        inOrderTraversalRec(root);
        System.out.println();
    }

    private void inOrderTraversalRec(Node root) {
        if (root != null) {
            inOrderTraversalRec(root.left);
            System.out.print(root.data + " ");
            inOrderTraversalRec(root.right);
        }
    }

    public void postOrderTraversal() {
        postOrderTraversalRec(root);
        System.out.println();
    }

    private void postOrderTraversalRec(Node root) {
        if (root != null) {
            postOrderTraversalRec(root.left);
            postOrderTraversalRec(root.right);
            System.out.print(root.data + " ");
        }
    }
}
```


``` java
public class Main {
    public static void main(String[] args) {
        IntegerBinaryTree tree = new IntegerBinaryTree();

        tree.insert(5);
        tree.insert(3);
        tree.insert(2);
        tree.insert(4);
        tree.insert(7);
        tree.insert(6);
        tree.insert(8);

        System.out.println("Pre-order traversal:");
        tree.preOrderTraversal();

        System.out.println("In-order traversal:");
        tree.inOrderTraversal();

        System.out.println("Post-order traversal:");
        tree.postOrderTraversal();

        System.out.println("Does the tree contain 60? " + tree.contains(60)); // true
        System.out.println("Does the tree contain 90? " + tree.contains(90)); // false

        System.out.println("Deleting 20 and 50 from the tree.");
        tree.delete(20);
        tree.delete(50);

        System.out.println("In-order traversal after deletion:");
        tree.inOrderTraversal();
    }
}

```

---


## 과제2 : 제네릭 이진 트리 구현

목표: 자바로 이진 트리(Binary Tree)를 구현한다.

**요구사항**

- 제네릭 클래스를 사용하여 다양한 데이터 타입을 저장할 수 있는 이진 트리(`BinaryTree`) 클래스를 구현한다.
- 제네릭은 Comparable을 상속받은 대상으로 한정한다 (`<T extends Comparable<T>>`)
- `BinaryTree` 클래스는 다음의 메소드를 포함해야 한다
  - `public void insert(T data)`: 트리에 새로운 노드를 삽입한다.
  - `public boolean contains(T data)`: 트리에서 지정된 데이터를 가진 노드가 있는지 확인한다.
  - `public void delete(T data)`: 트리에서 지정된 데이터를 가진 노드를 삭제한다.
  - `public void preOrderTraversal()`: 전위 순회(pre-order traversal)를 사용하여 트리의 모든 노드를 출력한다.
  - `public void inOrderTraversal()`: 중위 순회(in-order traversal)를 사용하여 트리의 모든 노드를 출력한다.
  - `public void postOrderTraversal()`: 후위 순회(post-order traversal)를 사용하여 트리의 모든 노드를 출력한다.

---

### 과제2를 수행하기 전에 `Comparable` 인터페이스에 대해서 알아보자

`Comparable` 인터페이스란?
- Java에서 객체들의 자연 순서를 정의하기 위해 사용되는 인터페이스로 객체에서 원하는 자료형으로 비교하기 위해, `Comparable` 인터페이스를 활용한다.
- 인터페이스를 구현한 클래스의 인스턴스는 서로 비교가 가능하며, 이를 통해 정렬이나 순서를 관리하는 작업을 수행할 수 있다.
- `Comparable` 인터페이스는 같은 자료형의 다른 객체 하나를 인자로 받아와 비교하는 `compareTo` 함수를 사용한다.
    - `public int compareTo(T o);`
    - 현재 객체가 매개변수 객체보다 작을 경우: 음수 값을 반환.
    - 현재 객체와 매개변수 객체가 같을 경우: 0을 반환.
    - 현재 객체가 매개변수 객체보다 클 경우: 양수 값을 반환.


---

###### tags: `과외(하희영)`