Check if only one single bit is set within an integer (whatever its position)

Question

I store flags using bits within a 64-bits integer.
I want to know if there is a single bit set whatever the position within the 64-bits integer (e.i. I do not care about the position of any specific bit).

boolean isOneSingleBitSet (long integer64)
{
   return ....;
}

I could count number of bits using the Bit Twiddling Hacks (by Sean Eron Anderson), but I am wondering what is the most efficient way to just detect whether one single bit is set...

I found some other related questions:

• (8051) Check if a single bit is set
• Detecting single one-bit streams within an integer

and also some Wikipedia pages:

• Find first one
• Bit manipulation
• Hamming weight

NB: my application is in java, but I am curious about optimizations using other languages...

---

EDIT: Lưu Vĩnh Phúc pointed out that my first link within my question already got the answer: see section Determining if an integer is a power of 2 in the Bit Twiddling Hacks (by Sean Eron Anderson). I did not realized that one single bit was the same as power of two.

Solution 1

If you just literally want to check if one single bit is set, then you are essentially checking if the number is a power of 2. To do this you can do:

if ((number & (number-1)) == 0) ...

This will also count 0 as a power of 2, so you should check for the number not being 0 if that is important. So then:

if (number != 0 && (number & (number-1)) == 0) ...

Solution 2

(using x as the argument)

Detecting if at least one bit is set is easy:

return x!=0;

Likewise detecting if bit one (second lowest bit) is set is easy:

return (x&2)!=0;

Exactly one bit is set iff it is a power of two. This works:

return x!=0 && (x & (x-1))==0;

Solution 3

The wrapper class java.lang.Long has a static function bitCount() that returns the number of bits in a long (64-bit int):

boolean isSingleBitSet(long l)
{
     return Long.bitCount(l) == 1;
}

Note that ints are 32-bit in java.

Solution 4

lets assume X is a 64bit inter full of 0s exept the one you are looking for;

  return ((64bitinteger&X)==X)

Solution 5

Assuming you have already an efficient - or hardware - implementation of ffs() - find first set - you may act as follows:

bool isOneSingleBitSet (long integer64)
{
   return (integer64 >> ffs(integer64)) == 0;
}

The ffs() function may be already available, or you may like to see your own link above

View more solutions

Comments

[Neil Coffey]

Changing the condition to ==1, this will work, but it almost certainly isn't the most efficient way of detecting a single bit, strictly speaking.

[John Dvorak]

Do you know the overhead of this method? This is certainly the most readable solution even if not the fastest.

[John Dvorak]

As it is now (>0), this will check for the number being non-zero (thanks @NeilCoffey for noticing).

[oHo]

is ffs() available in java?

[oHo]

ok... but how do you check if there is one single bit set? Do you check each 64 bits?

[oHo]

returns true when 64bitinteger = 0 :-(

[oHo]

+1 for this readable solution. Is there a function to check whether the integer is a power of two?

[oHo]

I am sorry, but I have tested your answer, I have these results: 0->false (ok) ; 1->true (ok) ; 2->false (KO) ; 3->false (ok) ; 4->false (KO) 5->false (ok) ... Please could you check it also on your side?

[oHo]

what is X in your answer? The same as 64bitinteger?

[oHo]

+1 your answer is valid :-) but tested using GCC __builtin_ffs(). Please tell me if ffs() is available in java...

[Neil Coffey]

Have a look at the second version where I've spelt out how it would look with the check for != 0. Really is fine as far as I can see.

[oHo]

Thank you for your edit, but your first line if ((number & (number-1)) == 0) ... does not check whether the number is a power of 2 as you can see within my test results (see my previous comment). To check whether the numberis a power of two, you can do: if (number && !(number & (number - 1)) ... (please accept my edit in your answer)

[Neil Coffey]

Not in Java you can't. In C, the line you wrote would be essentially equivalent to what I've written. If you want an answer relevant to C, not Java, then please amend and re-tag your question accordingly.

[Neil Coffey]

Jan - I'm guessing, just from the number of operations, that it would be basically a few times slower than the usual method that I mention in my answer. As for readability, you can wrap any implementation you want inside a method called isSingleBitSet() -- I'm not sure what difference it makes from that point of view...

[Neil Coffey]

...or put another way, actually have a look at the source code to Long.bitCount() and tell me how "readable" you think it is...!

[Ercan]

1010101 if you want to check if the 3rd bit is 1 1010101 & 0010000 equals to 0010000 in this example X=0010000

[Ali]

I am not a java developer! Just interested in your question

[Pursuit]

Using the method in this answer, yes, but I wouldn't recommend it. I understood the initial question as checking a specific bit, rather than checking for any single bit as intended. The question as you intended it is more interesting, and well answered by Neil Coffey and Jan Dvorak.

[ApproachingDarknessFish]

@olibre All powers of two except for 0 have exactly one bit--the questions are the same!

[oHo]

thanks for your answer but I am looking for the most efficient way to know if there is a single bit set at any position...

[oHo]

Thanks @Pursuit. I will improve a bit my question to be more understandable ;-)

[oHo]

My apologies, your first line is OK (except for zero as you say). And your second line is perfect :-) But I have rewarded @JanDvorak because he was the first to give the correct answer. Thank you very much for your help => +1

[Neil Coffey]

OK, though I did say verbally that you need to do the zero check: were you seriously unable to turn that into code??

[hl3mukkel]

Is there any way to check which bit is on? (beside log) Great trick by the way

[John Dvorak]

@hl3mukkel you could use iterated division (which is just a way to compute an integer logarithm). If you're looking for something faster, check stackoverflow.com/q/14429661/499214. Using a logarithm is definitely more readable, is subject to rounding issues.

[hl3mukkel]

Thanks! I found link to be an efficient & clean approach.