sehee

목차
1. char 자료형
  - limits.h 헤더 파일
2. scanf 오류
3. int 자료형
4. 이진탐색(Binary Search) 시 발생하는 오버플로우 대안

char 자료형

C언어에서는 정수 자료형인 char를 이용하여 문자 한 개를 저장함

이 때, char 자료형의 표현 범위는 -128~127이며, char에 문자를 저장할 때는 문자 자체를 저장하는 것이 아니라 문자에 해당하는 정수 값을 저장(ASCII)

(00000000~1111111까지 256가지 중 127까지 양수, 128부터 음수로 표현)

따라서, char로 선언한 변수에 ASCII 코드값 128을 저장한다면, 이에 overflow가 발생하여 -128이 됨

#include <stdio.h>
#include <limits.h>

int main() {
    printf("char min: %d, char max: %d\n", CHAR_MIN, CHAR_MAX);
    // char min: -128, char max: 127
    return 0;
}

scanf 오류가 발생하는 이유

보안 문제, 프로젝트에서 SDL(Security Development Lifecycle) 자동 검사를 수행하기 때문

문제: 문자열이나 파일에 대한 버퍼나 스택 등 메모리에 문제가 생길 수 있음

해결 방법

1) 코드 최상단에 #define _CRT_SECURE_NO_WARNINGS 추가

  - scanf 보안 경고로 인한 컴파일 에러 방지

2) scanf → scanf_s로 변경(visual studio에서만 호환 가능)

  - 메모리의 사이즈를 요구하는 함수(_s), C언어 표준 함수는 아님

3) scanf_s("%s", sentence, sizeof(sentence))라 명시(마지막에 sentence 사이즈)

(e.g. scanf_s(“%d”, &store, 10); → [10]개의 사이즈를 받는다고 명시)

[참고]

sscanf()란? 입력 대상: 표준 입력(X), 매개변수로 전달되는 문자열 버퍼(O)

fscanf()란? 입력 대상: 파일(f) 스트림에서 포맷 스트링에 맞게 데이터를 읽어들임

int 자료형

int 자료형의 표현 범위는 -2147483648~2147483647이며,

2,147,483,628 = 2³¹

따라서 부호 있는 32bit 정수가 보유할 수 있는 최대값은 2³¹-1 (int 범위: -2³¹ ~  2³¹-1)

#include <stdio.h>
#include <limits.h>

int main() {
    printf("int min: %d, int max: %d\n", INT_MIN, INT_MAX);
    // int min: -2147483648, int max: 2147483647
    return 0;
}

이진탐색(Binary Search)  시 발생하는 오버플로우 대안

first = 0;
last = n - 1;
middle = (first + last)/2;

부호 있는 32bit 정수가 보유할 수 있는 최대값이 2³¹-1임

이 때, 검색할 요소가 2³¹-2 (마지막에서 두번째 요소)라고 가정해 보자

[0, 1, 2, 3, … , 2³¹/2, …, (2³¹-3), (2³¹-2), (2³¹-1)]

첫 번째 반복 시 middle = (0 + (2³¹-1))/2

target은 해당 배열의 우측에 위치하므로,

first = middle + 1 = (2³¹-1)/2 + 1 = 2³⁰ + 1/2

(*)두 번째 반복 시, middle = (first + last)/2 = {(2³⁰ + 1/2) + (2³¹ - 1)}/2 = {(2³⁰ + 2³¹ - 1/2}/2 = 2²⁹+2³⁰-1/4 = 2²⁹(1+2) – 1/4 = 2³⁰ + 2²⁹ – 1/4 (= 2²⁹ * 3 – 1/4)

이 때 first = 2²⁹ * 3 – 1/4 + 1 = 2²⁹ * 3 + 3/4

세 번째 반복 시, middle = (first + last)/2 = {(2²⁹ + 2³⁰ + 3/4) +(2³¹ - 1)}/2 = 2³⁰ + 2²⁹ + 2²⁸ - 1/8

해당 함수를 n 번 반복 시, n번 째 middle = (2³⁰ + 2²⁹ + 2²⁸ + … + 2^(30-n)) - 1/2^(n)

원하는 값(2³¹-2)을 구하기까지 middle은 최대 2³¹을 넘지 않으므로 문제되지 않음

(∵ (2³⁰ + 2²⁹ + 2²⁸ + … + 2¹) = 2³¹ - 1 < 2³¹)

하지만 두 번째 연산 시,(*) first와 last의 합이 INT_MAX인 2³¹ - 1을 넘어가게 되어 오버플로우 발생

➡️ middle이 음수가 됨

따라서, middle 값을 다음과 같이 변경하여 문제 해결 가능

문제: first와 last의 합이 2³¹을 초과하게 되어 overflow 발생

기존 연산: middle = (first + last)/2;

변경 연산1: middle = first + (last – first)/2;

변경 연산2: middle. = ((unsigned int)first + (unsigned int)last)) >> 1

* unsigned int는 sign(부호)가 없는 정수형으로,

Overflow된 값을 정상적인 값으로 판단하여 unsigned 연산에서 고의적으로 wrap around 이용

[참고자료]

The curious case of Binary Search - The famous bug that remained undetected for20 years

https://thebittheories.com/the-curious-case-of-binary-search-the-famous-bug-that-remained-undetected-for-20-years-973e89fc212