如何检查int中是否只设置了一位？

Question

我有一个std::uint32_t，想要检查是否设置了确切的一位。如何在不遍历所有位的情况下执行此操作？换句话说，可以简化以下功能吗？

static inline bool isExactlyOneBitSet(std::uint32_t bits)
{
    return ((bits & 1) == bits
        || (bits & 1 << 1) == bits
        || (bits & 1 << 2) == bits
        // ...
        || (bits & 1 << 31) == bits
        );
}

奖励：如果返回值是找到的一位或为0，那将是很好的。

static inline bool isExactlyOneBitSet(std::uint32_t bits)
{
if (bits & 1) {return 1;}
else if  (bits & 1 << 1) {return 1 << 1;};
//...
else if  (bits & 1 << 31) {return 1 << 31;};

return 0;
}

Answer 1

因此，您想知道数字是否为2的幂？好吧，有一个著名的算法可以做到，

check_bit(std::uint32_t bits)
{
    return bits && !(bits & (bits-1));
}

2乘以1的任何幂就是全部1s。例如，

4 - 1 = 3 (011)
8 - 1 = 7 (0111)

按位与2的任意幂且比其小任何1的幂0。因此，我们可以使用表达式验证数字是否为2的幂n&(n-1)。

会在时失败n=0，因此我们必须添加一个额外and条件。

为了找到钻头的位置，您可以执行以下操作：

int findSetBit(std::uint32_t bits)
{
    if (!(bits && !(bits & (bits-1))))
        return 0;
    return log2(bits) + 1;
}

额外的东西

在gcc中，您可以使用__builtin_popcount()来查找任意数量的设置位数。

#include <iostream>

int main()
{
   std::cout << __builtin_popcount (4) << "\n";
   std::cout << __builtin_popcount (3) << "\n";

   return 0;
}

然后检查计数是否相等1。

关于计数，还有另一种著名的算法Brian Kernighan的算法。谷歌它，它发现log(n)时间计数。

Answer 2

这是您的奖金问题的解决方案（当然，这也是您原始问题的解决方案）：

std::uint32_t exactlyOneBitSet(std::uint32_t bits) {
    return bits&(((bool)(bits&(bits-1)))-1);
}

使用 clang 在 x86_64 上仅编译 4 条指令：

0000000000000000 <exactlyOneBitSet(unsigned int)>:
   0:   8d 4f ff                lea    -0x1(%rdi),%ecx
   3:   31 c0                   xor    %eax,%eax
   5:   85 f9                   test   %edi,%ecx
   7:   0f 44 c7                cmove  %edi,%eax
   a:   c3                      retq