C++에서 두 바이너리의 합에서 첫 번째 캐리가 있는 가장 오른쪽 비트의 위치

이 문제에서 두 개의 양의 정수 N과 M이 주어집니다. 우리의 임무는 N과 M의 합을 이진법으로 더할 때 첫 번째 캐리 비트를 생성하는 맨 오른쪽 비트를 인쇄하는 것입니다. .

문제를 이해하기 위해 예를 들어보겠습니다.

입력 - N =5, M =14

출력 - 3

설명 -

(5)2 = 0101 , (14)2 = 1110
Sum 0101
+   1110
    10011

이 문제를 해결하기 위해 부울 대수에서 몇 가지 관찰을 고려할 것입니다.

합계는 두 숫자가 모두 1일 때 캐리를 생성합니다. 따라서 캐리가 생성되는 모든 비트를 찾습니다. 이것은 두 숫자의 검색 및 연산에 의해 수행됩니다. 그리고 숫자의 가장 오른쪽 비트를 찾습니다.

이 방법을 사용하여 예제를 해결해 보겠습니다.

N = 5 and M = 14
N&M = 0100

여기에서 가장 오른쪽에 있는 비트는 인덱스 3에 있습니다.

예시

솔루션 구현을 보여주는 프로그램,

#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