ตำแหน่งบิตขวาสุดที่มีการคาร์รี่แรกในผลบวกของสองจำนวนไบนารีใน C++

ในปัญหานี้ เราได้รับจำนวนเต็มบวกสองตัว N และ M งานของเราคือพิมพ์บิตขวาสุดที่สร้างคาร์รี่บิตแรกในการบวกไบนารีของผลรวมของ N และ M

มาดูตัวอย่างเพื่อเข้าใจปัญหา:

Input - N = 5, M = 14

Output - 3

Explanation -

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

เพื่อแก้ปัญหานี้ เราจะพิจารณาบางข้อสังเกตจากพีชคณิตบูลีน

ผลรวมจะสร้างคาร์รี่เมื่อทั้งสองตัวเลขเป็น 1 ดังนั้นเราจะหาบิตทั้งหมดที่สร้างคาร์รี่ สิ่งนี้จะทำได้โดยการหาการดำเนินการ AND ของทั้งสองตัวเลข และหาบิตขวาสุดของตัวเลขนั้น

สิ่งนี้ดูซับซ้อนเล็กน้อย มาแก้ตัวอย่างด้วยวิธีนี้:

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