ในปัญหานี้ เราได้รับการแสดงเลขฐานสองของตัวเลข และเราต้องหาการแทนค่าเลขฐานสองของตัวเลขก่อนหน้า นั่นคือตัวเลขที่เกิดขึ้นหลังจากลบหนึ่งตัวออกจากตัวเลขที่กำหนด
การแทนค่าไบนารี ของตัวเลขกำลังเปลี่ยนฐานของตัวเลขเป็นฐาน 2 และแทนตัวเลขโดยใช้เพียง 0 หรือ 1
ตัวอย่างเช่น การแทนค่าไบนารีของ 23 คือ 10111
ตรงนี้เราจะได้ตัวเลข สมมุติว่า n ในรูปเลขฐานสอง และเราต้องหาการแทนค่าไบนารีของ n-1
เพื่อแก้ปัญหานี้ เราต้องรู้พื้นฐานของการลบเลขฐานสอง มาดูกันว่าจะเกิดอะไรขึ้นเมื่อ 1 ถูกลบออกจาก 0 หรือ 1 ในรูปแบบไบนารี 0 - 1 =1 + 1 ทบจากบิตถัดไป 1 - 1 =0.
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากันดีกว่า
Input : 101101100 Output : 101101011 Explanation : (101101100)2 Is the binary representation of 364. The number preceding it is 363 whose binary representation is (101101011)2 . we have used binary subtraction here and subtracted (1)2 from the binary representation of the number to yield the result .
มาดูตรรกะเบื้องหลังโปรแกรมนี้กัน จากนั้นเราจะออกแบบอัลกอริทึมตามตรรกะของเรา ที่นี่เราต้องลบหนึ่งจากการแทนค่าเลขฐานสองของตัวเลข สำหรับสิ่งนี้เราจะเริ่มจากทางขวาและพลิกศูนย์ทั้งหมดเป็น 1 จนกว่าจะพบ 1 เมื่อพบ 1 เราจะพลิก 1 เป็น 0 และส่งคืนผลลัพธ์สุดท้าย
อัลกอริทึม
Step 1 : Start right to left i.e n-1 to 0. Step 2 : If 1 is encounter change it to 0 and break. Step 3 : If 0 is encountered, change it 1. Step 4 : Print the array.
ตัวอย่าง
การใช้งานโปรแกรมของอัลกอริธึมข้างต้น -
#include <bits/stdc++.h>
using namespace std;
string previousNumber(string num) {
int n = num.size();
if (num.compare("1") == 0)
return "0";
int i;
for (i = n - 1; i >= 0; i--) {
if (num.at(i) == '1') {
num.at(i) = '0';
break;
} else
num.at(i) = '1';
}
if (i == 0)
return num.substr(1, n - 1);
return num;
}
int main() {
string number = "1011011000";
cout<<"the Binary representation of the number is "<<number<<endl;
cout<<"Binary representation of previous number is "<<previousNumber(number);
return 0;
} ผลลัพธ์
The Binary representation of the number is 1011011000 Binary representation of previous number is 1011010111
