C 프로그램으로 숫자를 2^X – 1 형태로 만드는 단계 출력하기

주어진 숫자 n을 XOR(배타적 논리합) 연산을 활용해 2^X – 1 형태로 변환하고, 그 과정의 모든 단계를 출력하는 프로그램을 C 언어로 작성하는 방법을 알아보겠습니다.

문제 규칙

• 홀수 번째 단계에서는 숫자에 임의의 2^M – 1 값(M은 직접 선택)을 XOR 연산합니다.
• 짝수 번째 단계에서는 숫자를 1만큼 증가시킵니다.

n이 2^X – 1 형태가 될 때까지 위 두 단계를 반복 수행하며, 진행된 모든 단계를 순서대로 출력합니다.

예시

입력: 22
출력:
    Step 1 : Xor with 15
    Step 2: Increase by 1
    Step 3 : Xor with 7
    Step 4: Increase by 1
    Step 5 : Xor with 1

입력: 7
출력: No Steps to be performed

숫자 7은 이미 2³ – 1 = 7이므로 어떠한 연산도 수행할 필요가 없습니다. 따라서 "No Steps to be performed"라는 메시지가 출력됩니다.

알고리즘

핵심 아이디어는 다음과 같습니다. 먼저 n에서 가장 왼쪽에 있는 설정되지 않은 비트(unset bit)의 위치를 찾습니다. 이 비트가 존재하지 않는다면 n은 이미 2^X – 1 형태입니다. 존재한다면 홀수 단계에서 해당 위치까지의 모든 비트를 1로 채우는 값인 2^m – 1과 XOR 연산을 수행하고, 짝수 단계에서는 1을 더해 줍니다.

int find_leftmost_unsetbit(int n)
START
STEP 1 : DECLARE AND ASSIGN ind = -1, i = 1
STEP 2 : LOOP WHILE n
   IF !(n & 1) THEN,
      ASSIGN ind WITH i
   END IF
   INCREMENT i BY 1
   LEFT SHIFT n BY 1
END WHILE
STEP 3 : RETURN ind
STOP

void perform_steps(int n)
START
STEP 1 : DECLARE AND ASSIGN left = find_leftmost_unsetbit(n)
STEP 2 : IF left == -1 THEN,
   PRINT "No Steps to be performed"
   RETURN
END IF
STEP 3 : DECLARE AND ASSIGN step = 1
STEP 4 : LOOP WHILE find_leftmost_unsetbit(n) != -1
   IF step % 2 == 0 THEN,
      INCREMENT n BY 1
      PRINT "Step n : Increase by 1\n"
   ELSE
      DECLARE AND ASSIGN m = find_leftmost_unsetbit(n)
      AND SET num = (pow(2, m) - 1)
      SET n = n ^ num
      PRINT "Step N : Xor with Num"
   END IF
   INCREMENT step BY 1
END LOOP
STOP

find_leftmost_unsetbit 함수

이 함수는 숫자 n을 오른쪽 시프트하면서 각 비트를 검사하여, 값이 0인 비트 중 가장 왼쪽(상위)에 있는 위치의 인덱스를 반환합니다. 설정되지 않은 비트가 하나도 없으면 -1을 반환하여 이미 목표 형태임을 알려 줍니다.

perform_steps 함수

단계 카운터(step)를 기준으로 짝수 단계면 n을 1 증가시키고, 홀수 단계면 find_leftmost_unsetbit로 찾은 위치 m을 이용해 2^m – 1 값을 계산한 뒤 n과 XOR 연산을 수행합니다. 이 과정을 n이 2^X – 1 형태가 될 때까지 반복합니다.

C 언어 구현 예제

#include <stdio.h>
#include <math.h>
// 가장 왼쪽의 unset 비트를 찾는 함수
int find_leftmost_unsetbit(int n){
    int ind = -1;
    int i = 1;
    while (n) {
        if (!(n & 1))
            ind = i;
        i++;
        n >>= 1;
    }
    return ind;
}
void perform_steps(int n){
    // 가장 왼쪽의 unset 비트 찾기
    int left = find_leftmost_unsetbit(n);
    // unset 비트가 없다면 이미 2^x - 1 형태
    if (left == -1) {
        printf("No Steps to be performed\n");
        return;
    }
    // 단계 수를 세는 변수
    int step = 1;
    // 숫자가 2^x - 1 형태가 될 때까지 반복
    while (find_leftmost_unsetbit(n) != -1) {
        // 짝수 단계라면 1 증가
        if (step % 2 == 0) {
            n += 1;
            printf("Step %d: Increase by 1\n", step);
        }
        // 홀수 단계라면 2^m - 1과 XOR 연산
        else {
            // 가장 왼쪽의 unset 비트 찾기
            int m = find_leftmost_unsetbit(n);
            int num = (int)(pow(2, m) - 1);
            n = n ^ num;
            printf("Step %d : Xor with %d\n", step, num);
        }
        // 단계 증가
        step += 1;
    }
}
int main(){
    int n = 22;
    perform_steps(n);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

Step 1 : Xor with 15
Step 2 : Increase by 1
Step 3 : Xor with 7
Step 4 : Increase by 1
Step 5 : Xor with 1

동작 원리 살펴보기

입력값 22(이진수 10110)를 예로 들어 보겠습니다. 첫 번째 단계에서 가장 왼쪽의 unset 비트는 4번째 위치이므로 2⁴ – 1 = 15와 XOR 연산을 수행합니다. 10110 ⊕ 01111 = 11001(25)이 되고, 다음 단계에서 1을 더해 26(11010)이 됩니다. 이후 같은 방식으로 7과 XOR한 뒤 1을 더하고, 마지막으로 1과 XOR하면 31(11111), 즉 2⁵ – 1 형태에 도달하게 됩니다.