이 문제에서는 두 개의 양의 정수 N과 M이 주어집니다. 우리의 과제는 N과 M을 이진수로 더할 때 첫 번째 캐리(carry) 비트를 생성하는 가장 오른쪽 비트의 위치를 출력하는 것입니다.
문제 이해하기
예시를 통해 문제를 살펴보겠습니다.
입력 − N = 5, M = 14
출력 − 3
설명 −
(5)₂ = 0101 , (14)₂ = 1110
합계:
0101
+ 1110
--------
10011위의 덧셈 과정을 보면, 세 번째 비트(오른쪽에서부터)에서 두 숫자가 모두 1이므로 첫 번째 캐리가 발생합니다.
해결 접근 방법
이 문제는 불 대수(Boolean Algebra)의 기본 원리를 활용해 해결할 수 있습니다.
두 수를 더할 때 캐리는 두 비트가 모두 1일 때만 발생합니다. 따라서 다음 단계로 문제를 풀 수 있습니다.
- N과 M에 대해 AND(&) 연산을 수행하여 캐리가 발생하는 모든 비트 자리를 찾습니다.
- 결과값에서 가장 오른쪽에 있는 설정된(set) 비트의 위치를 구합니다.
다소 복잡하게 들릴 수 있으니, 예시를 통해 확인해 보겠습니다.
N = 5, M = 14 N & M = 0101 & 1110 = 0100
결과인 0100에서 가장 오른쪽에 설정된 비트는 인덱스 3에 위치합니다. 이것이 바로 우리가 찾고자 하는 첫 번째 캐리가 발생하는 비트의 위치입니다.
C++ 구현 예제
위 해결 방법을 구현한 프로그램입니다.
#include <iostream>
#include <math.h>
using namespace std;
int rightSetBit(int N) {
int bitIndex = log2(N & -N) + 1;
return bitIndex;
}
void rightCarryBit(int N, int M) {
int carryIndex = rightSetBit(N & M);
cout << carryIndex;
}
int main() {
int N = 4, M = 14;
cout << "The position of rightmost bit that generates carry in the sum of "
<< N << " and " << M << " is ";
rightCarryBit(N, M);
return 0;
}출력 결과
The position of rightmost bit that generates carry in the sum of 4 and 14 is 3
코드 설명
rightSetBit() 함수는 N & -N 연산을 사용합니다. 이는 비트 조작(bit manipulation)의 고전적인 기법으로, 어떤 수와 그 수의 음수(2의 보수)를 AND 연산하면 가장 오른쪽에 설정된 비트만 남게 됩니다. 여기에 log₂를 취하고 1을 더하면 해당 비트의 인덱스(1부터 시작하는 위치)를 얻을 수 있습니다.
rightCarryBit() 함수는 N과 M의 AND 연산 결과에 대해 위 함수를 호출함으로써, 첫 번째 캐리가 발생하는 비트의 위치를 손쉽게 계산합니다.
이 알고리즘의 시간 복잡도는 O(1)로, 매우 효율적입니다.