C 프로그래밍으로 이진수의 후행 0과 선행 0 개수 구하기

이진수 프로그래밍에서 자주 다뤄지는 개념인 후행 0(Trailing Zeros)과 선행 0(Leading Zeros)에 대해 알아보겠습니다. 두 값 모두 비트 시프트와 AND 연산만으로 간단하게 계산할 수 있습니다.

후행 0(Trailing Zeros)이란?

후행 0이란 이진수에서 최하위 비트(LSB) 쪽 끝에 연속해서 위치한 0들을 의미합니다. 즉, LSB에서 시작해 처음으로 1인 비트를 만나기 전까지 등장하는 0의 개수를 말합니다.

예시

10진수 104를 이진수로 변환하면 다음과 같습니다.

(MSB) 1101000 (LSB)

여기서 사용된 용어의 의미는 다음과 같습니다.

MSB(Most Significant Bit): 최상위 비트
LSB(Least Significant Bit): 최하위 비트
LSB 쪽 끝에서 첫 번째 1이 나타나기 전까지 0이 세 개 이어져 있습니다.
따라서 104의 후행 0 개수는 3개입니다.

후행 0 개수 세기 프로그램

다음은 입력받은 숫자의 후행 0 개수를 계산하는 C 프로그램입니다. 오른쪽 시프트 연산자(>>)를 사용해 낮은 자리 비트부터 차례로 검사하고, 처음 1이 발견되면 반복을 종료합니다.

#include<stdio.h>
#include<stdlib.h>
int main(){
    int number, i, trail = 0, size;
    printf("Enter a number\n");
    scanf("%d",&number);
    size = sizeof(number) * 8;
    for(i = 0; i < size; i++){
        if((number >> i) & 1) {
            break;
        }
        trail++;
    }
    printf("Number of trailing ZERO is = %d", trail);
    return 0;
}

동작 원리

sizeof(number) * 8을 통해 정수형 변수의 전체 비트 수(일반적으로 32비트)를 구합니다.
숫자를 i칸 오른쪽으로 시프트한 뒤 1과 AND 연산하면 i번째 비트의 값을 알 수 있습니다.
결과가 1이면 해당 비트가 설정된 것이므로 반복을 멈추고, 0이면 카운터를 1씩 증가시킵니다.

실행 결과

Enter a number
24
Number of trailing ZERO is = 3

24의 이진수 표현은 11000이므로 후행 0은 3개로 출력됩니다.

선행 0(Leading Zeros)이란?

반대로, 비트가 1로 설정되기 전까지 MSB 쪽에 위치한 0들을 선행 0이라고 합니다. 즉, 최상위 비트에서 아래로 내려가며 처음 1을 만나기 전까지의 연속된 0의 개수입니다.

예시

10진수 94를 32비트 정수 기준으로 이진수로 표현하면 다음과 같습니다.

(MSB) .....001011110 (LSB)

첫 번째 1이 나타나기 전까지의 0은 총 25개입니다.

선행 0 개수 세기 프로그램

다음은 입력받은 숫자의 선행 0 개수를 계산하는 C 프로그램입니다. 왼쪽 시프트 연산자(<<)와 MSB 마스크 값을 활용해 높은 자리 비트부터 차례로 검사합니다.

#include<stdio.h>
#include<stdlib.h>
int main(){
    int number, i, lead = 0, Msb,size;
    printf("Enter a number\n");
    scanf("%d",&number);
    size = sizeof(number) * 8;
    Msb=1<<(size-1);
    for(i = 0; i < size; i++){
        if((number << i) & Msb) {
            break;
        }
        lead++;
    }
    printf("Number of Leading ZERO is = %d", lead);
    return 0;
}

동작 원리

Msb = 1 << (size - 1)로 최상위 비트만 1인 마스크를 만듭니다.
숫자를 i칸 왼쪽으로 시프트하면 i번째 비트가 MSB 위치로 이동하므로, 마스크와 AND 연산해 그 비트를 검사할 수 있습니다.
결과가 0이면 해당 비트도 0이라는 뜻이므로 선행 0 카운터를 증가시키고, 1을 만나면 반복을 종료합니다.

실행 결과

Enter a number
94
Number of Leading ZERO is = 25

이처럼 비트 시프트와 AND 연산만으로 이진수의 후행 0과 선행 0 개수를 손쉽게 구할 수 있습니다. 이러한 비트 조작 기법은 알고리즘 문제 풀이나 임베디드 프로그래밍에서 특히 유용하게 활용됩니다.