ในปัญหานี้ เราได้รับการแสดงเลขฐานสองของตัวเลข และเราต้องหาการแทนค่าเลขฐานสองของตัวเลขถัดไป นั่นคือ ตัวเลขที่ได้ผลลัพธ์หลังจากบวกหนึ่งไปยังตัวเลขที่กำหนด
การแทนค่าไบนารี ของตัวเลขกำลังเปลี่ยนฐานของตัวเลขเป็นฐาน 2 และแทนตัวเลขโดยใช้เพียง 0 หรือ 1
ตัวอย่างเช่น การแทนค่าไบนารีของ 14 คือ 1110
ตรงนี้เราจะได้ตัวเลข สมมุติว่า n ในรูปเลขฐานสอง และเราต้องหาการแทนค่าไบนารีของ n+1
เพื่อแก้ปัญหานี้ เราจำเป็นต้องรู้พื้นฐานของการบวกเลขฐานสอง มาดูกันว่าจะเกิดอะไรขึ้นเมื่อ 1 ถูกเพิ่มเข้ากับ 0 หรือ 1 ในรูปแบบไบนารี
0 + 1 =1
1 + 1 =10
ตัวอย่าง
มาดูตัวอย่างวิธีแก้ปัญหาข้างต้นกัน
Input: 010010111 Output: 010011000 Explanation : (010010111)2 is the binary representation of 152 and the next number will be 153 whose binary representation is (010011000)2. We will use binary addition here and add binary (1)2 to the binary representation of the number.
จากตัวอย่างข้างต้น เราจะเห็นได้ว่าเมื่อบวกเลขฐานสอง 1 เข้ากับตัวเลขแล้ว ทุก ๆ ตัวที่เริ่มต้นจากขวาจะถูกแปลงเป็น 0 จนกว่าจะพบ 0 ตัวแรกและ 0 นี้จะถูกพลิกเป็น 1 ตอนนี้ เรามาสร้างอัลกอริทึมสำหรับตรรกะนี้กัน
อัลกอริทึม
Step 1 : Start right to left i.e n-1 to 0 Step 2 : If 0 is encountered, change it 1 and break Step 3 : If one is encounter change it to 0. Step 4 : When no zero is encountered, add 1 to the start of the array. Step 5 : Print the array.
ตัวอย่าง
ทีนี้มาดูการใช้งานโค้ดของอัลกอริทึมนี้กัน
#include <bits/stdc++.h>
using namespace std;
string nextBinary(string num) {
int l = num.size();
int flag = 0 ;
for (int i=l-1; i>=0; i--) {
if (num.at(i) == '0') {
num.at(i) = '1';
flag = 1;
break;
} else
num.at(i) = '0';
}
if (flag < 0)
num = "1" + num;
return num;
}
int main() {
string number = "0111010111";
cout<<"The Binary representation of the number is "<<number<<endl;
cout<<"Binary representation of next number is "<<nextBinary(number);
return 0;
} ผลลัพธ์
The Binary representation of the number is 0111010111 Binary representation of next number is 0111011000
