檢查數字是否具有交替模式的位 - C++ 中 O(1) 方法

讓我們考慮一個整數 n。問題在於檢查該整數的二進位制等價物中是否有交替模式。交替模式即 101010....

方法如下：計算 num = n XOR (n >> 1)，現在，如果 num 的所有位均為 1，則 num 具有交替模式。

示例

 實際演示

#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

阿納布·查克拉伯蒂

更新日期: 21-10-2019

394 次瀏覽

開啟你的 職業生涯

完成課程即可獲得認證

開始