Trong bài toán này, chúng ta được cho hai số nguyên dương N và M. Nhiệm vụ của chúng ta là in ra bit ngoài cùng bên phải tạo ra bit mang đầu tiên trong phép cộng nhị phân của tổng N và M .
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào - N =5, M =14
Đầu ra - 3
Giải thích -
(5)2 = 0101 , (14)2 = 1110 Sum 0101 + 1110 10011
Để giải quyết vấn đề này, chúng ta sẽ xem xét một số quan sát từ đại số boolean.
Tổng sẽ tạo ra giá trị mang khi cả hai số đều là 1. Vì vậy, chúng tôi sẽ tìm tất cả các bit nơi mang được tạo ra. Điều này sẽ được thực hiện bằng cách tìm và hoạt động của cả hai số. Và tìm bit tận cùng bên phải của số.
Điều này có vẻ hơi phức tạp để hiểu, hãy cùng giải quyết một ví dụ bằng phương pháp này.
N = 5 and M = 14 N&M = 0100
Một bit đặt ngoài cùng bên phải ở đây là chỉ số 3.
Ví dụ
Chương trình cho thấy việc triển khai giải pháp của chúng tôi,
#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;
} Đầu ra
The position of rightmost bit that generates carry in the sum of 4 and 14 is 3