ตัวเลขก่อนหน้าเท่ากับ 1's Complement ใน C++

ในปัญหานี้ เราได้รับจำนวนเต็ม n งานของเราคือตรวจสอบว่าเลขก่อนหน้าเท่ากับ 1's complement ของตัวเลขหรือไม่

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

Input: 12 Output: No
Explanation: (12)10 = (1100)2
Preceding number 11 = (1011)2
1's complement of 12 = (0011)2

Input: 4 Output: Yes
Explanation: 4 = (100)2
Preceding number 3 = (011)2
1's complement of 12 = (011)2

ในการแก้ปัญหานี้ เราสามารถใช้วิธีง่ายๆ ซึ่งคือการเปรียบเทียบเลขก่อนหน้าและ 1's complement ของตัวเลข

วิธีนี้ง่ายแต่อยู่พื้นที่และเวลา time complexity: O(n)

วิธีแก้ปัญหาที่มีประสิทธิภาพอาจเป็นการใช้วิธีทั่วไปที่เราค้นหาเพื่อแก้ปัญหา ที่นี่ เฉพาะตัวเลขที่เป็นกำลังของ 2 จะทำให้เงื่อนไขเป็นจริง คือ เลขก่อนหน้าเท่ากับ 1's complement

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

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

#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<<"Both are the same";
    else
        cout<<"Both aren't the same";
    return 0;
}

ผลลัพธ์

Both are the same