Số nguyên nhỏ hơn trước đó có một bit set ít hơn trong C++

Trong bài toán này, chúng ta được cho một số nguyên n. Nhiệm vụ của chúng ta là in số lớn nhất nhỏ hơn n có thể tạo được bằng cách thay đổi một bit set của biểu diễn nhị phân của số đó.

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào: n = 3
Đầu ra: 2
Giải thích: (3)10 = (011)₂
Lật một bit set cho 001 và 010. 010 lớn hơn tức là 2.

Để giải quyết bài toán này, chúng ta sẽ phải lật bit set bên phải nhất và làm cho nó thành 0, điều này sẽ tạo ra số lớn nhất có thể nhỏ hơn n được tìm thấy bằng cách lật một bit của số.

Chương trình minh họa triển khai giải pháp của chúng ta:

Ví dụ

#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<<"Số là "<<n<<"\nSố nguyên lớn nhất nhỏ hơn số là : ";
    previousSmallerInteger(n);
    return 0;
}

Kết quả

Số là 3452
Số nguyên lớn nhất nhỏ hơn số là : 3448