C : 변수 / 2의 보수 / 형식 지정자 / Jump Table

Nekoder

---

1. 변수 타입

 

Type	Size	Range
char	1 byte	unsigned char = 0 ~ 255, signed char = -128 ~ 127
short	2 bytes	unsigned short = 0 ~ 65,535, signed short = -32,768 ~ 32,767
int	4 bytes	unsigned int = 0 ~ 4,294,967,295 signed int = -2,147,483,648 ~ 2,147,483,647
long	4 bytes	unsigned long = 0 ~ 18446744073709551615, signed long = -9223372036854775808 ~ 9223372036854775807
long long	8 bytes	unsigned long = 0 ~ 18446744073709551615, signed long = -9223372036854775808 ~ 9223372036854775807
float	4 bytes	±3.4 × 10³⁸ , (7 decimal places)
double	8 bytes	±1.8 × 10³⁰⁸ , (15 decimal places)
long double	16 bytes	±1.1 × 10⁴⁹³² , (18 ~ 19 decimal places)

---

2. 2의 보수

 

2의 보수, 1) 모든 비트를 반전시킨 후 2) 1을 더해야하는 번거로운 보수 방식

이라고 생각 할 수있다.

1의 보수가 존재하긴 하지만 실제 연산할 때는 2의 보수를 이용하는 게 훨씬 편하기 때문(컴퓨터 기준, 사람 기준으로는 연산시간?)

 

연산방식	과정	결과	추가연산
1의 보수 연산	0000_0111 (7) 1111_1010 (-5) ----------------- 0000_0001 (2) 1 (캐리 발생) ----------------- 0000_0010 (2)	2	carry 보정 추가 연산 필요
2의 보수 연산	0000_0111 (7) 1111_1011 (-5) ----------------- 0000_0010 (2)	2	보수 변환 후 연산하여 연산 수가 적음

 

---

3. scanf format specifier

 

Type	Format Specifier	Example input
char	%c	A
char[]	%s	Hello
short	%hd	123
int	%d	12
long	%ld	1234567890
long long	%lld	123456789
float	%f	3.14
double	%lf	3.141592
long double	%Lf	3.1415926535

---

4. Short Circuit Optimization

 

Short-Circuit Optimization이란 논리 연산자(&&, ||)를 사용할 때, 불필요한 연산을 생략하는 최적화 기법
즉, 결과가 확정되면 나머지 조건을 평가하지 않고 바로 반환하여 불필요한 연산을 줄이고, 성능을 최적화할 수 있다.

#include <stdio.h>

int funcA() {
    printf("Executing A\n");
    return 0;  // 항상 false 반환
}

int funcB() {
    printf("Executing B\n");
    return 1;  // 항상 true 반환
}

int main() {
    printf("Short-Circuit Test 시작!\n");

    if (funcA() && funcB()) {  // funcA()가 false이므로 funcB() 실행 안 됨
        printf("AND condition met\n");
    }

    if (funcA() || funcB()) {  // funcA()가 false이므로 funcB() 실행됨
        printf("OR condition met\n");
    }

    return 0;
}

위 코드를 컴파일하면 

아래와 같은 결과가 나옵니다

Short-Circuit Test 시작!
Executing A
Executing A
Executing B
OR condition met

 

 

Short-Circuit Optimization의 동작 방식

&& (AND 연산자)

if (funcA() && funcB()) { ... }

• funcA()가 false(0)이면, funcB()를 평가하지 않고 바로 false 반환
• funcA()가 true(1)이면, funcB()까지 평가 후 최종 결과 결정
• funcA()가 false일 가능성이 높다면, 앞쪽에 배치하는 것이 성능적으로 유리하다

|| (OR 연산자)

if (funcA() || funcB()) { ... }

• funcA()가 true(1)이면, funcB()를 평가하지 않고 바로 true 반환
• funcA()가 false(0)이면, funcB()까지 평가 후 최종 결과 결정
• funcA()가 true일 가능성이 높다면, 앞쪽에 배치하는 것이 성능적으로 유리하다

 

 

 

어셈블리 코드를 뜯어보면 최적화를 찾을 수 있습니다.

 

Short-Circuit Optimization을 확인하는 어셈블리 코드 분석

 

C 코드에서 &&와 || 연산이 Short-Circuit 최적화가 적용되는지 확인하려면 어셈블리 코드를 살펴봐야 한다.
GCC를 사용해 어셈블리 코드를 확인할 수 있다.

어셈블리 코드 확인 방법

gcc -S short_circuit.c -o short_circuit.s cat short_circuit.s

 

&& 연산에 대한 어셈블리 코드

call funcA# funcA() 호출
testl %eax, %eax # funcA()의 반환값이 0인지 확인
je .L1 # funcA() == 0이면 funcB() 실행하지 않고 .L1으로 점프 (Short-Circuit 적용)
call funcB # funcA()가 true이면 funcB() 실행
testl %eax, %eax # funcB()의 반환값 확인
je .L1

• funcA()가 false(0)이면 .L1으로 점프하여 funcB() 실행을 건너뜀
• funcA()가 true(1)이면 funcB()를 실행하여 최종 결과 결정

|| 연산에 대한 어셈블리 코드

call funcA # funcA() 호출
testl %eax, %eax # funcA()의 반환값이 0인지 확인
jne .L2 # funcA() != 0이면 funcB() 실행하지 않고 .L2으로 점프 (Short-Circuit 적용)
call funcB # funcA()가 false이면 funcB() 실행
testl %eax, %eax # funcB()의 반환값 확인
je .L3

• funcA()가 true(1)이면 .L2로 점프하여 funcB() 실행을 건너뜀
• funcA()가 false(0)이면 funcB()까지 실행 후 최종 결과 결정

---

Jump Table

 

 

Jump Table은 switch-case 문과 같은 다중 분기 구조를 효율적으로 처리하기 위한 기법이다.
일반적으로 if-else 문을 사용하는 경우 조건을 하나씩 비교해야 하지만, 점프 테이블을 사용하면 O(1) 시간 복잡도로 즉시 해당 코드로 이동할 수 있다.

위 그림을 보면 Table1과 Table2라는 두 개의 테이블이 있다.

 

1. Table1: 인덱스와 값 저장

• i2 값에 따라 특정한 Value가 저장
• 이 값은 Table2에서 특정 위치를 찾기 위한 인덱스 역할.
• 예를 들어, i2 = 3일 때 Value = 9이면, Table2에서 offset이 9인 위치를 찾아 점프.

2. Table2: 오프셋(Offset)과 실제 주소 저장

• Table1에서 가져온 Value 값을 기반으로 Table2의 특정 위치를 찾음.
• Table2는 해당 offset에 대응하는 함수 주소를 저장하고 있음.
• 예를 들어, Value = 9라면 Table2에서 offset 9에 있는 주소로 점프해서 특정 case를 실행하는 방식.

3. Case Operation: 실제 함수 실행

• Table2에서 가져온 주소를 사용해서 해당 함수(f1, f2, f3 등)를 실행
• C++에서 switch-case 문이 어셈블리로 변환될 때, 각 case에 해당하는 주소를 저장해서 빠르게 실행할 수 있도록 만듦.
• 결과적으로 "i 값에 따라 case 문을 실행하는 시간을 O(1)으로 줄이는 방식".

 

빠른 분기 처리

• if-else 문을 사용하면 최악의 경우 O(n)만큼 비교해야 하지만,
• 점프 테이블을 사용하면 "O(1)"로 바로 해당 주소로 이동할 수 있음.

어셈블리 수준에서 최적화 가능

• 컴파일러는 switch-case 문을 점프 테이블로 변환할 수 있어 실행 속도를 향상시킴.

코드 크기 감소

• if-else 블록을 많이 사용하면 코드 크기가 커질 수 있지만, 점프 테이블은 간결한 구조를 유지할 수 있음.

 

O(1)이란? (상수 시간 복잡도)

O(1)은 시간 복잡도(Time Complexity)의 표현 중 하나로, 입력 크기(n)에 관계없이 일정한 시간이 걸리는 연산을 의미한다.
즉, 데이터 크기가 증가해도 실행 시간에는 영향이 거의 없고, 항상 일정한 시간 내에 수행되는 알고리즘이다.

---

점프 테이블에서 O(1)이 적용되는 이유

점프 테이블은 switch-case 문에서 특정 case로 바로 이동할 수 있도록 미리 함수 주소를 저장한 배열을 활용한다.
이 방식에서는 추가적인 조건 비교 없이 바로 특정 case로 이동할 수 있기 때문에 O(1)의 시간 복잡도를 가진다.

 

일반적인 if-else 문 vs 점프 테이블

방법시간 복잡도설명

if-else	O(n)	여러 조건을 순차적으로 비교해야 함
점프 테이블	O(1)	인덱스를 기반으로 바로 case를 실행

즉, if-else 문은 조건을 하나씩 비교해야 하기 때문에 최악의 경우 O(n)의 성능을 보이지만,
점프 테이블은 한 번의 테이블 조회만으로 즉시 해당 case로 이동할 수 있으므로 O(1)의 성능을 보인다.

---

O(1) 예제 코드 (배열 접근 vs if-else 비교)

 

O(1) - 배열을 이용한 점프 테이블

void case1() { printf("Case 1\n"); }
void case2() { printf("Case 2\n"); }
void case3() { printf("Case 3\n"); }

void (*jumpTable[4])() = { NULL, case1, case2, case3 };

void switch_case(int i) {
    if (i >= 1 && i <= 3)
        jumpTable[i]();  // O(1) - 바로 해당 함수 실행
    else
        printf("Default case\n");
}

• jumpTable[i]()를 사용하면 배열을 통해 바로 함수 주소를 참조하므로 O(1)
• 추가적인 조건 비교 없이 한 번의 연산만으로 특정 case를 실행

O(n) - if-else 문을 사용한 방식

void switch_case(int i) {
    if (i == 1)
        case1();
    else if (i == 2)
        case2();
    else if (i == 3)
        case3();
    else
        printf("Default case\n");
}

• i == 3일 경우, 최악의 경우 3번의 비교 연산을 수행해야 함
• n개의 case가 있다면, 최대 n번의 비교가 필요하므로 O(n)

---

결론

점프 테이블을 사용하면 연산 횟수를 줄이고, 특정 case로 바로 이동할 수 있기 때문에 O(1)의 성능을 보인다.
즉, 입력 값이 커져도 연산 시간이 변하지 않고 일정한 속도를 유지하는 것이 O(1)의 핵심 개념이다.

하지만, 자주 사용되는 연산을 if-else 문의 제일 앞에 둔다면, 연산 속도와 메모리를 모두 줄일 수도 있다.

 

•  

Nekoder