检查数字是否具有交替模式的位 - 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 次浏览

开启你的 职业生涯

完成课程即可获得认证

开始