Kiểm tra bit luân phiên (alternating pattern) O(1) trong C++

Kiểm tra số nguyên có mẫu bit luân phiên (101010...) hay không. Cách O(1): tính num = n ^ (n >> 1). Nếu mọi bit của num đều là 1 thì n có mẫu luân phiên.

Kiểm tra all bits set: ((num + 1) & num) == 0.

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; // 101010
    if(hasAlternatePattern(number))
        cout << "Has alternating pattern";
    else
        cout << "Has no alternating pattern";
}

Kết quả

Has alternating pattern