C++で2つのバイナリの合計が最初にキャリーされる右端のビットの位置

この問題では、2つの正の整数NとMが与えられます。私たちのタスクは、NとMの合計の2進加算で最初のキャリービットを生成する右端のビットを出力することです。 。

問題を理解するために例を見てみましょう

入力 − 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