Kiểm tra số thưa (sparse number) trong C++

Số thưa (sparse number) là số mà biểu diễn nhị phân không có hai bit 1 liên tiếp. Ví dụ 72 = 01001000₂ → không có 11 liên tiếp → là sparse.

Kiểm tra: n & (n >> 1). Nếu kết quả = 0 → sparse.

Ví dụ

#include <iostream>
using namespace std;

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

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

Kết quả

This is sparse number