9

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.

Community
  • 1
  • 1
oHo
  • 51,447
  • 27
  • 165
  • 200
  • 1
    For Java I would consider using BitSet class for this purpose which supports convenient isEmpty() method as well as many others making bit flags much easier to use. – maximdim Nov 16 '12 at 16:17
  • 1
    it's already in the Bit Twiddling Hacks linked above: [Determining if an integer is a power of 2](http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2) – phuclv Oct 04 '15 at 09:31
  • Oh! Thank you :-) I update my question :-) Cheers – oHo Oct 05 '15 at 07:42
  • Does this answer your question? [How to check if a number is a power of 2](https://stackoverflow.com/questions/600293/how-to-check-if-a-number-is-a-power-of-2) – Tsyvarev Apr 09 '20 at 08:44

6 Answers6

25

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) ...
Neil Coffey
  • 21,615
  • 7
  • 62
  • 83
  • 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 Nov 16 '12 at 17:08
  • 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. – Neil Coffey Nov 16 '12 at 17:17
  • 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 `number`is a power of two, you can do: `if (number && !(number & (number - 1)) ...` (please accept my edit in your answer) – oHo Nov 16 '12 at 17:25
  • 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 Nov 16 '12 at 17:33
  • 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 – oHo Nov 19 '12 at 14:30
  • 4
    OK, though I did say verbally that you need to do the zero check: were you seriously unable to turn that into code?? – Neil Coffey Nov 19 '12 at 16:30
17

(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;
John Dvorak
  • 26,799
  • 13
  • 69
  • 83
  • Is there any way to check which bit is on? (beside log) Great trick by the way – hl3mukkel Mar 21 '14 at 17:54
  • @hl3mukkel you could use iterated division (which is just a way to compute an integer logarithm). If you're looking for something faster, check http://stackoverflow.com/q/14429661/499214. Using a logarithm is definitely more readable, is subject to rounding issues. – John Dvorak Mar 22 '14 at 07:07
  • Thanks! I found [link](http://stackoverflow.com/a/20342282/2489327) to be an efficient & clean approach. – hl3mukkel Mar 22 '14 at 07:35
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.

oHo
  • 51,447
  • 27
  • 165
  • 200
ApproachingDarknessFish
  • 14,133
  • 7
  • 40
  • 79
  • 2
    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. – Neil Coffey Nov 16 '12 at 16:25
  • Do you know the overhead of this method? This is certainly the most readable solution even if not the fastest. – John Dvorak Nov 16 '12 at 16:29
  • As it is now (`>0`), this will check for the number being non-zero (thanks @NeilCoffey for noticing). – John Dvorak Nov 16 '12 at 16:30
  • +1 for this readable solution. Is there a function to check whether the integer is a power of two? – oHo Nov 16 '12 at 16:59
  • 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 Nov 16 '12 at 17:40
  • ...or put another way, actually have a look at the source code to Long.bitCount() and tell me how "readable" you think it is...! – Neil Coffey Nov 16 '12 at 17:41
  • @olibre All powers of two except for 0 have exactly one bit--the questions are the same! – ApproachingDarknessFish Nov 16 '12 at 20:11
1

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

Ali
  • 9,440
  • 12
  • 62
  • 92
1

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

  return ((64bitinteger&X)==X)
Ercan
  • 3,705
  • 1
  • 22
  • 37
  • returns true when `64bitinteger = 0` :-( – oHo Nov 16 '12 at 16:44
  • what is `X` in your answer? The same as `64bitinteger`? – oHo Nov 16 '12 at 17:12
  • 1010101 if you want to check if the 3rd bit is 1 1010101 & 0010000 equals to 0010000 in this example X=0010000 – Ercan Nov 16 '12 at 17:42
  • 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 Nov 17 '12 at 00:36
0

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  );
Pursuit
  • 12,285
  • 1
  • 25
  • 41
  • ok... but how do you check if there is one single bit set? Do you check each 64 bits? – oHo Nov 16 '12 at 16:43
  • 1
    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. – Pursuit Nov 16 '12 at 18:19
  • Thanks @Pursuit. I will improve a bit my question to be more understandable ;-) – oHo Nov 17 '12 at 00:39