Kiểm tra xem một số nhất định có thưa thớt hay không trong C ++

Trong phần này, chúng ta sẽ xem cách kiểm tra một số có bị thưa hay không. Một số được cho là thưa thớt nếu biểu diễn nhị phân của số đó, không có hai hoặc nhiều hơn hai số 1 liên tiếp. Giả sử một số giống như 72. Đây là 01001000. Ở đây không có hai hoặc nhiều số 1 liên tiếp.

Để kiểm tra một số có thưa hay không, chúng ta sẽ lấy số đó là n, sau đó dịch số đó sang phải một bit và thực hiện theo chiều dọc bit AND. nếu kết quả là 0 thì đó là một số thưa thớt, ngược lại thì không.

Ví dụ

#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";
   }
}

Đầu ra

This is sparse number