ตรวจสอบ Sparse Number ใน C++

ในส่วนนี้จะตรวจสอบว่า Number เป็น Sparse หรือไม่ Sparse Number คือ Binary Representation ไม่มี 1 ติดกัน 2 ตัวขึ้นไป ตัวอย่าง 72 = 01001000 ไม่มี 1 ติดกัน

วิธีตรวจสอบ: n & (n >> 1) ถ้าผลลัพธ์เป็น 0 คือ Sparse Number มิฉะนั้นไม่ใช่

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

#include <iostream>
using namespace std;

bool isSparseNumber(int n) {
    int res = n & (n >> 1);
    if(res == 0)
        return true;
    return false;
}

int main() {
    int num = 72;
    if(isSparseNumber(num)) {
        cout << "This is sparse number";
    } else {
        cout << "This is not sparse number";
    }
}

ผลลัพธ์

This is sparse number