C++에서 두 수의 비트를 번갈아 조합해 새로운 숫자 만들기

이 문제에서는 두 숫자의 비트를 번갈아 사용해 새로운 숫자를 생성해야 합니다. 두 번째 숫자(m)의 첫 번째 비트(LSB)에서 시작하여, 첫 번째 숫자(n)의 두 번째 비트, 다시 두 번째 숫자의 세 번째 비트, 첫 번째 숫자의 네 번째 비트와 같은 방식으로 두 수의 비트를 교대로 선택하는 것이 핵심입니다.

문제 이해하기

예제를 통해 문제를 더 명확하게 이해해 보겠습니다.

입력 : n = 6, m = 10
출력 : 2

설명 :
비트 위치  :  3  2  1  0
n = 6     :  0  1  1  0
m = 10    :  1  0  1  0
선택 비트  :  n  m  n  m
--------------------------------
결과      :  0  0  1  0  = 2

예제에서 알 수 있듯이, 결과 값은 두 번째 숫자(m)의 최하위 비트(LSB)부터 시작해 두 수의 비트를 번갈아 가져와 만든 것입니다. 즉, 홀수 번째 비트(1번째, 3번째)는 m에서, 짝수 번째 비트(2번째, 4번째)는 n에서 가져온다고 생각하면 됩니다.

접근 방법

이 문제를 해결하는 실용적인 방법은 다음과 같습니다. 먼저 첫 번째 숫자 n에서 짝수 번째 비트만 남긴 값을 구하고, 다음으로 두 번째 숫자 m에서 홀수 번째 비트만 남긴 값을 구한 뒤, 두 값을 비트 OR(|) 연산으로 결합하면 원하는 결과를 얻을 수 있습니다.

알고리즘

1단계 : n에 대해 짝수 번째 비트만 설정된 값을 구한다.
2단계 : m에 대해 홀수 번째 비트만 설정된 값을 구한다.
3단계 : 결과(result) = (n의 짝수 번째 비트) | (m의 홀수 번째 비트)
4단계 : 결과값을 출력한다.

C++ 구현

#include <iostream>
using namespace std;
int setevenbits(int n) ;
int setoddbits(int m) ;
int main(){
    int n = 12;
    int m = 17;
    int setn = setevenbits(n);
    int setm = setoddbits(m);
    int result = ( setn | setm );
    cout<<result;
    return 0;
}
int setevenbits(int n){
    int temp = n;
    int count = 0;
    int res = 0;
    for (temp = n; temp > 0; temp >>= 1) {
        if (count % 2 == 1)
            res |= (1 << count);
        count++;
    }
    return (n & res);
}
int setoddbits(int m){
    int count = 0;
    int res = 0;
    for (int temp = m; temp > 0; temp >>= 1) {
        if (count % 2 == 0)
            res |= (1 << count);
        count++;
    }
    return (m & res);
}

실행 결과

25

코드 동작 원리 (n = 12, m = 17)

setevenbits(12) : 12는 2진수로 01100입니다. 루프를 돌며 비트 인덱스(count)가 홀수인 위치(1, 3)만 마스크(res)에 설정한 후, n과 AND(&) 연산을 수행하면 01000, 즉 8이 됩니다.

setoddbits(17) : 17은 2진수로 10001입니다. 같은 방식으로 비트 인덱스가 짝수인 위치(0, 2, 4)만 마스크에 설정한 후, m과 AND 연산을 수행하면 10001, 즉 17이 됩니다.

마지막으로 두 값을 OR 연산으로 결합하면 01000 | 10001 = 11001이 되어, 최종적으로 25가 출력됩니다.

복잡도 분석

두 함수 모두 숫자의 비트 개수만큼만 반복하므로 시간 복잡도는 O(log n)이며, 별도의 추가 공간을 거의 사용하지 않으므로 공간 복잡도는 O(1)입니다.