Kiểm tra xem một số có các bit trong mẫu thay thế không - Set-2 O (1) Cách tiếp cận trong C ++

Hãy coi chúng tôi có một số nguyên n. Vấn đề là phải kiểm tra xem số nguyên này có các mẫu thay thế trong hệ nhị phân tương đương của nó hay không. Mẫu thay thế có nghĩa là 101010….

Cách tiếp cận như sau:tính num =n XOR (n>> 1), bây giờ nếu tất cả các bit của num là 1, thì num có các mẫu xen kẽ.

Ví dụ

#include <iostream>
#include <algorithm>
using namespace std;
bool isAllBitSet(int n){
   if (((n + 1) & n) == 0)
      return true;
   return false;
}
bool hasAlternatePattern(unsigned int n) {
   unsigned int num = n ^ (n >> 1);
   return isAllBitSet(num);
}
int main() {
   unsigned int number = 42;
   if(hasAlternatePattern(number))
      cout << "Has alternating pattern";
   else
      cout << "Has no alternating pattern";
}

Đầu ra

Has alternating pattern