I have an std::uint32_t and want to check if exactly one bit is set. How can I do this without iterating over all bits like this? In other words, can the following function be simplified?
static inline bool isExactlyOneBitSet(std::uint32_t bits)
{
return ((bits & 1) == bits
|| (bits & 1 << 1) == bits
|| (bits & 1 << 2) == bits
// ...
|| (bits & 1 << 31) == bits
);
}
Bonus: It would be nice if the return value was the one found bit or else 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;
}
So you want to know if a number is power of 2 or not? Well there is a famous algorithm for that, you can simply do,
check_bit(std::uint32_t bits)
{
return bits && !(bits & (bits-1));
}
Any power of 2 when subtracted by 1 is all 1s. e.g,
4 - 1 = 3 (011)
8 - 1 = 7 (0111)
The bitwise and of any power of 2 and any number 1 less than it will give 0. So we can verify if a number is power of 2 or not by using the expression, n&(n-1).
It will fail when n=0, so we have to add an extra and condition.
For finding the position of bit, you can do:
int findSetBit(std::uint32_t bits)
{
if (!(bits && !(bits & (bits-1))))
return 0;
return log2(bits) + 1;
}
In gcc, you can use __builtin_popcount(), to find the count of set bits in any number.
#include <iostream>
int main()
{
std::cout << __builtin_popcount (4) << "\n";
std::cout << __builtin_popcount (3) << "\n";
return 0;
}
Then check if count is equal to 1 or not.
Regarding count, there is another famous algorithm, Brian Kernighan’s Algorithm. Google it up, it finds count in log(n) time.
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加