c++ - 如何检查 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 都是 1。例如，

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

2 的任何幂和任何小于它的数 1 的按位与将得到 0。因此，我们可以使用表达式 n&(n-1) 来验证一个数是否为 2 的幂。

当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 算法。 Google 一下，它找到了 log(n) 时间的计数。