数字的二进制表示是否是交替位，例如。10101010、1010等

找到了答案 这很简单

    return (n & (n>>1)) == 0;

你的想法

(n & (n>>1)) == 0只会检查是否有连续的 1。

您还需要检查是否每 2 位设置一次：

• 如果是这种情况，则应使用 ，应设置连续位n | (n >> 1u)
• 将 1 添加到上一个结果将使其成为 2 的幂（或溢出的 0）
• n & (n-1)是一种删除最低有效（最右边）设置位的方法（并在 2 的幂下这样做会导致 0）n

对于边缘情况

• 对于 ，是 2 的幂。0(0+1)
• 对于 ，我们的结果为 == ，这也给出了所有未设置的位:)0b101010..100xFFFF..FF + 10

结果：

constexpr bool is_alternative_bit(std::uint32_t n)
{
    const bool has_consecutive1 = (n & (n >> 1u)) != 0;
    const auto less_signifiant_bit_cleared = [](auto n){ return n & (n - 1u); };

    return !has_consecutive1 && (less_signifiant_bit_cleared((n | (n >> 1u)) + 1u) == 0);
}

演示

这是我在看到@Jarod42在他的回答中巧妙地使用之前写的答案。n & (n - 1)

最终，我的解决方案失败了，因为它违反了 O（1） 规范，因为它在 的位上运行循环。（请参阅下面的功能。nmask_leading_zeros

我的解决方案确实有一件事是可读性。它以一个由交替位组成的常量开始：

    std::uint32_t const alt{ 0b0101'0101'0101'0101'0101'0101'0101'0101 };

数一数。有 16 个 1 和 16 个零。

取补码 ， 生成唯一一个具有交替位的其他 32 位整数。~alt

接下来，我在前导零出现的地方创建一个零，并在其他任何地方创建一个 1。maskn

    auto const mask{ mask_leading_zeros(n) };

此掩码可用于掩码应将 0 和 引出的内容。如果由交替位组成，则必须是 或 。alt~altnnalt & mask~alt & mask

这些观察结果导致以下功能：

bool has_alternating_bits(std::uint32_t const n) {
    std::uint32_t const alt{ 0b0101'0101'0101'0101'0101'0101'0101'0101 };
    auto const mask{ mask_leading_zeros(n) };
    return (alt & mask) == n || (~alt & mask) == n;
}

就像我说的，很好，可读性很强。当然，当我写的时候，我确实违反了规范：mask_leading_zeros

std::uint32_t mask_leading_zeros(std::uint32_t const n) {
    std::uint32_t mask{};
    for (std::uint32_t bit_number{ 32u }; bit_number--;) {
        auto const bit{ 1u << bit_number };
        if (n & bit)
            break;
        mask |= bit;
    }
    return ~mask;
}

以下是我用于测试的程序的完整内容：

// main.ixx
export module main;
import std;

std::uint32_t mask_leading_zeros(std::uint32_t const n) {
    std::uint32_t mask{};
    for (std::uint32_t bit_number{ 32u }; bit_number--;) {
        auto const bit{ 1u << bit_number };
        if (n & bit)
            break;
        mask |= bit;
    }
    return ~mask;
}
bool has_alternating_bits(std::uint32_t const n) {
    std::uint32_t const alt{ 0b0101'0101'0101'0101'0101'0101'0101'0101 };
    auto const mask{ mask_leading_zeros(n) };
    return (alt & mask) == n || (~alt & mask) == n;
}
std::string bit_string(std::uint32_t const n) {
    return std::format("{:b}", n);
}
export int main() {
    std::cout << std::format("{:>5}  {}  {} \n"
        , 'n'
        , '*'
        , "bit_string(n)"
    );
    for (std::uint32_t n{}; n <= 10; ++n)
        std::cout << std::format("{:5}  {}  {} \n"
            , n
            , (has_alternating_bits(n) ? '*' : ' ')
            , bit_string(n)
        );
    for (std::uint32_t const& n : { 20u, 21u, 42u, 43u, 84u, 85u, 170u, 171u, 340u, 341u})
        std::cout << std::format("{:5}  {}  {} \n"
            , n
            , (has_alternating_bits(n) ? '*' : ' ')
            , bit_string(n)
        );
}
// end file: main.ixx

输出：

    n  *  bit_string(n)
    0  *  0
    1  *  1
    2  *  10
    3     11
    4     100
    5  *  101
    6     110
    7     111
    8     1000
    9     1001
   10  *  1010
   20     10100
   21  *  10101
   42  *  101010
   43     101011
   84     1010100
   85  *  1010101
  170  *  10101010
  171     10101011
  340     101010100
  341  *  101010101

这只需 5 个操作即可完成（取决于您如何计算操作，但我们不要争论这一点）：

bool is_alternating(uint32_t x)
{
    uint32_t y = x << 1;
    return (x & (y + (y | 3))) == x;
}

请参阅 ideone 上的输出。

包括 0 和 1，因为它们是交替的模式，尽管长度分别为 0 和 1（所以它们看起来不是交替的，而只是因为没有足够的位来真正显示模式）。

该模式是一种常用的习惯用语，用于测试是否是 的子集。这里。(x & S) == xxSS = y + (y | 3) = (x << 1) + ((x << 1) | 3)

成为子集的意义和意义相当复杂，我不是随便想出来的。该解决方案是使用 CEGIS（CounterExample 引导归纳综合）的实现找到的，因此由计算机生成。SxS

如果是偶数，则在这种情况下等价于 。让我们将 as 的位命名为 （零在那里，因为是偶数），因此 .xSS = (x << 2) | 3xabcd0xS = abcd011

• d0始终是 的子集，任意两个位都是 的子集。1111
• cd是 if 且仅 if 的子集。01c = 0
• bc是 if 且仅当d0b <= d and c = 0
• ab是 if 且仅当cda <= c and b <= d

现在为了成为 1，也必须是 1，它不可能是，所以.另一方面可以是 1，即 if 也是 1。这些模式继续存在，偶数位置的位（从索引零开始，最低有效位）必须全部为零，而偶数位可以一直到某个点为 1，一旦其中一个位为零，那么左侧的其余部分也必须全部为零。aca = 0bd

如果为奇数，则在这种情况下等价于 。让我们将 as 的位命名为 （那个在那里，因为很奇怪），因此 .xSS = (x << 2) | 1xabcd1xS = abcd101

• d1是 if 且仅 if 的子集。01d = 0
• cd是 if 且仅 if 但我们已经知道的子集。10d = 0
• bc是 if 且仅当d1b <= d
• ab是 if 且仅当cda <= c and b <= d

然后，这些位以与以前类似的方式关联，但偶数位和奇数位的角色互换。

---

其他人找到了一个更短的解决方案：

bool is_alternating(uint32_t x)
{
    uint32_t y = x << 2;
    return (x | y) <= (y | 2);
}