C++로 두 숫자의 가장 왼쪽 서로 다른 비트 위치 찾기

문제 설명

이 문제에서는 두 개의 정수 num1과 num2가 주어지며, 두 숫자를 이진수로 표현했을 때 왼쪽에서 처음으로 서로 다른 비트(최상위 불일치 비트)의 위치를 찾아 출력하는 것이 목표입니다.

두 이진수의 자릿수가 다를 경우 올바른 비교를 위해 자릿수가 적은 숫자 앞에 0을 채워 길이를 동일하게 맞춰야 합니다.

입력 예시

num1 = 4, num2 = 7

출력 예시

1

설명

숫자 4의 이진 표현은 100입니다.

숫자 7의 이진 표현은 111입니다.

왼쪽에서 첫 번째 비트가 서로 다르므로 결과는 1이 됩니다.

해결 접근 방법

이 문제를 해결하는 한 가지 방법은 먼저 두 숫자의 비트 길이를 맞추는 것입니다. 자릿수가 작은 숫자에 2^{(비트 길이 차이)}를 곱하면 됩니다.

그다음 두 숫자에 대해 XOR 연산을 수행합니다. XOR 연산은 두 숫자의 비트가 서로 다른 위치에서만 1을 반환하므로, 결과값에서 가장 높은 자리의 1이 있는 위치를 찾으면 그것이 곧 첫 번째로 다른 비트의 위치입니다. 여기서 전체 비트 수와 XOR 결과의 비트 수를 활용해 원하는 위치를 계산할 수 있습니다.

알고리즘

1단계 − 자릿수가 작은 숫자에 (2 ^ (비트 길이 차이))를 곱하여 두 숫자의 비트 길이를 동일하게 맞춥니다.

2단계 − num1과 num2에 대해 XOR 연산을 수행합니다.

3단계 − 최종 비트 차이 위치는 (전체 비트 수 − XOR 결과의 비트 수 + 1)로 계산합니다.

구현 예제

#include <iostream>
#include <math.h>
using namespace std;
int findmisMatchBit(int num1, int num2) {
    if (num1 == num2)
        return 0;
    int num1Size = floor(log2(num1)) + 1;
    int num2Size = floor(log2(num2)) + 1;
    int BitSizeDiff = abs(num1Size - num2Size);
    int maxBitSize = max(num1Size, num2Size);
    if (num1Size > num2Size)
        num2 *= pow(2, BitSizeDiff);
    else
        num1 *= pow(2, BitSizeDiff);
    int XOR = num1 ^ num2;
    int XORBitSize = floor(log2(XOR)) + 1;
    return (maxBitSize - XORBitSize + 1);
}
int main() {
    int num1 = 43, num2 = 765;
    cout<<"The position of leftmost dis-similar bit of the two
    number is "<<findmisMatchBit(num1, num2);
    return 0;
}

실행 결과

The position of leftmost dis-similar bit of the two number is 4

위 코드에서 num1은 43, num2는 765로 설정되어 있습니다. 두 숫자의 이진 표현을 비교하면 왼쪽에서 네 번째 비트가 처음으로 서로 다르므로 프로그램은 4를 출력합니다.