CODEWITHSUNDEEP
javabinarybit-manipulationbitbitwise-operators
oHo
oHo

Reputation: 54541

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

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:

and also some Wikipedia pages:

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.

Upvotes: 10

Views: 15413

Answers (6)

Neil Coffey
Neil Coffey

Reputation: 21795

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) ...

Upvotes: 27

ApproachingDarknessFish
ApproachingDarknessFish

Reputation: 14313

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.

Upvotes: 3

John Dvorak
John Dvorak

Reputation: 27277

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

Upvotes: 18

Ercan
Ercan

Reputation: 3705

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

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

Upvotes: 1

Pursuit
Pursuit

Reputation: 12345

Seems like you can do a bitwise AND with a long representation of the single bit you want to check. For example, to check the LSB

return(   (integer64 & 1L)!=0  );

Or to check the 4th bit from the right

return(   (integer64 & 8L)!=0  );

Upvotes: 0

Ali
Ali

Reputation: 9830

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

Upvotes: 1

Related Questions