จำนวนเต็มก่อนหน้าที่เล็กกว่าที่มีจำนวน Set Bit น้อยกว่า 1 ใน C++

ในปัญหานี้ เราได้รับจำนวนเต็ม n งานของเราคือพิมพ์จำนวนที่ใหญ่ที่สุดน้อยกว่า n ซึ่งสามารถสร้างได้โดยการเปลี่ยนหนึ่ง set bit ของ binary representation ของตัวเลข

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

Input: n = 3 Output: 2
Explanation: (3)10 = (011)2
Flipping one set bit gives 001 and 010.
010 is greater i.e. 2.

ในการแก้ปัญหานี้ เราจะต้องพลิก rightmost set bit ให้เป็นศูนย์ ซึ่งจะสร้างตัวเลขที่เป็นไปได้มากที่สุดน้อยกว่า n ที่พบจากการพลิกหนึ่งบิตของตัวเลข

โปรแกรมแสดงการนำวิธีแก้ปัญหาของเราไปใช้

ตัวอย่างโค้ด

#include<iostream>
#include<math.h>
using namespace std;

int returnRightSetBit(int n) {
    return log2(n & -n) + 1;
}

void previousSmallerInteger(int n) {
    int rightBit = returnRightSetBit(n);
    cout<<(n&~(1<<(rightBit - 1)));
}

int main() {
    int n = 3452;
    cout<<"The number is "<<n<<"\nThe greatest integer smaller than the number is : ";
    previousSmallerInteger(n);
    return 0;
}

ผลลัพธ์

The number is 3452
The greatest integer smaller than the number is : 3448