Số trước đó giống như phần bù 1 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à kiểm tra xem số trước đó có bằng phần bù 1 của số đó hay không.

Hãy xem một vài ví dụ để hiểu bài toán của chúng ta:

Đầu vào: 12
Đầu ra: Không
Giải thích: (12)10 = (1100)₂
Số trước đó 11 = (1011)₂
Phần bù 1 của 12 = (0011)₂

Đầu vào: 4
Đầu ra: Có
Giải thích: 4 = (100)₂
Số trước đó 3 = (011)₂
Phần bù 1 của 12 = (011)₂

Để giải quyết bài toán này, chúng ta có thể sử dụng một cách tiếp cận đơn giản là so sánh số trước đó và phần bù 1 của số.

Cách tiếp cận này đơn giản nhưng tốn không gian và thời gian. Độ phức tạp thời gian: O(n)

Một giải pháp hiệu quả hơn có thể là sử dụng phương pháp chung mà chúng ta tìm kiếm để giải quyết bài toán. Ở đây, chỉ các số là lũy thừa của 2 mới thỏa mãn điều kiện, tức là số trước đó bằng phần bù 1.

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

Ví dụ

#include <iostream>
using namespace std;
bool sameBits(unsigned long int n){
    if ((n & (n - 1)) == 0)
        return true;
    return false;
}
int main(){
    unsigned long int n = 64;
    if(sameBits(n))
        cout<<"Cả hai là giống nhau";
    else
        cout<<"Cả hai không giống nhau";
    return 0;
}

Kết quả

Cả hai là giống nhau