ตรวจสอบ Alternating Bit Pattern แบบ O(1) ใน C++

พิจารณา Integer n ต้องการตรวจสอบว่า Binary Representation มี Alternating Pattern (101010...) หรือไม่

วิธี O(1): คำนวณ num = n XOR (n >> 1) ถ้า Bits ทั้งหมดของ num เป็น 1 แสดงว่ามี Alternating Pattern

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

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

ผลลัพธ์

Has alternating pattern