How to check if exactly one bit is set in an int?

Question

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;
}

The number which is 2^n are only numbers which has one bit set. — Atul Kumar, Jun 29 '18 at 05:03
_exactly_ one or _at least_ one? Your first example checks for at least one, which is equivalent to `!= 0`. — tkausl, Jun 29 '18 at 05:03
Explained [here](https://stackoverflow.com/q/1053582/509868) — anatolyg, Jun 29 '18 at 05:06
FWIW, C++20 will likely have [`std::ispow2`](https://en.cppreference.com/w/cpp/numeric/ispow2). — chris, Jun 29 '18 at 05:11
There are several other questions about this with great answers, e.g. https://stackoverflow.com/questions/15951776/ or https://stackoverflow.com/questions/23856596/ but none fulfills the bonus question... — Fabian, Jun 29 '18 at 05:18

Abhishek Keshri · Accepted Answer · 2018-06-29T05:51:09.527

18

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;
}

Extra Stuffs

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.

edited Jun 29 '18 at 05:51

answered Jun 29 '18 at 05:23

Abhishek Keshri

2,864
11
30

https://stackoverflow.com/questions/11114017/whats-the-difference-between-popcnt-and-mm-popcnt-u32 for an overview of the cross platform cross compiler variants of __buildtin_popcount – Guillaume Gris Jun 29 '18 at 05:56
thanks for mentioning that link, the `popcount` function is compiler dependent. – Abhishek Keshri Jun 29 '18 at 05:59
In the bonus, isn't the desired value bits, not log2 of bits? – Jeff Garrett Jun 29 '18 at 10:21
The op wants to find the position of the 'on' bit. – Abhishek Keshri Jun 29 '18 at 10:27

score 2 · Answer 2 · answered Jun 29 '18 at 06:27

Here's a solution for your bonus question (and of course, it is a solution for your original question as well):

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

This compiles down to only 4 instructions on x86_64 with clang:

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

How to check if exactly one bit is set in an int?

2 Answers2

Extra Stuffs