ในปัญหานี้ เราได้รับจำนวนเต็มบวกสองจำนวน 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
