Vị trí bit phải nhất có carry đầu tiên khi cộng hai số nhị phân trong C++

Trong bài toán này, cho hai số nguyên dương N và M. Nhiệm vụ in vị trí bit phải nhất tạo ra bit carry đầu tiên khi cộng nhị phân N và M.

Ví dụ minh họa:

Đầu vào - N = 5, M = 14

Kết quả - 3

Giải thích -

(5)2 = 0101 , (14)2 = 1110 
Cộng:  0101 + 1110 = 10011

Để giải bài toán, xét quan sát từ đại số Boole.

Cộng sẽ tạo carry khi cả hai bit đều là 1. Ta tìm tất cả bit tạo carry bằng phép AND của hai số. Sau đó tìm bit phải nhất của kết quả.

Ví dụ minh họa phương pháp:

N = 5, M = 14 
N & M = 0100 
Bit 1 phải nhất ở chỉ số 3.

Chương trình minh họa

#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 << "Vị trí bit phải nhất tạo carry khi cộng " << N << " và " << M << " là "; 
    rightCarryBit(N, M); 
    return 0; 
}

Kết quả

Vị trí bit phải nhất tạo carry khi cộng 4 và 14 là 3