Test if a bitboard have only one bit set to 1

Question

I have a bitboard and I want to check in C if there is ONLY one bit set to 1.

#include <stdint.h>
typedef uint64_t bboard;
bboard b = 0x0000000000000010;
if (only_one_bit_set_to_one (b)) // in this example expected true
  // do something...

Any idea to write the function int only_one_bit_set_to_one (bboard b)?

score 59 · Accepted Answer · answered Sep 18 '12 at 19:40

59

Sure, it's easy:

int only_one_bit_set_to_one (bboard b)
{
    return b && !(b & (b-1));
}

Say b has any bits set, the least significant is bit number k. Then b-1 has the same bits as b for indices above k, a 0-bit in place k and 1-bits in the less significant places, so the bitwise and removes the least significant set bit from b. If b had only one bit set, the result becomes 0, if b had more bits set, the result is nonzero.

answered Sep 18 '12 at 19:40

Daniel Fischer

181,706
17
308
431

3

ah, the old "is power of two" algoritm – S.C. Madsen Sep 18 '12 at 19:41
Thanks very much! and can you tell me how to test if all 1 bits are in odd or even positions? – Pioz Sep 18 '12 at 19:46
1

XOR with a mask consisting of say all odd bit positions set to 1, followed by an AND with the same mask, if the result is equal to the mask, the bit was NOT in an odd position (I think)... – S.C. Madsen Sep 18 '12 at 19:52
1

`int all_bits_in_even_positions(bboard b) { return !(b & 0xAAAAAAAAAAAAAAAA); }`, `int all_bits_in_odd_positions(bboard b) { return !(b & 0x5555555555555555); }`, that is assuming you count positions from 0 (for the 2^0 valued bit), and not from 1. – Daniel Fischer Sep 18 '12 at 19:53
Daniel seems to agree, so give it ago :-) – S.C. Madsen Sep 18 '12 at 19:54
Why not just `if (b == 0xAAAA...)` and `if (b == 0x5555...)` if we know the type of `b`? – ouah Sep 18 '12 at 19:55
@ouah as I understood it, e.g. 5 has all its 1-bits in even positions, it's not required that all bits in even/odd positions are set. – Daniel Fischer Sep 18 '12 at 20:07
1

@DanielFischer my bad, I think I misunderstood the question. – ouah Sep 18 '12 at 20:09
Aren't you supposed to write (b - (bboard) 1) ? otherwise 1 could be in 32 bits. – David 天宇 Wong Oct 28 '13 at 23:40
@David天宇Wong The usual arithmetic conversions (6.3.1.8) take care of that. The `int` with value `1` is converted to `bboard`, unless `int` has greater conversion rank than `int64_t` and can represent all values of `uint64_t`. But then nothing's lost if `b` is converted to `int`. – Daniel Fischer Oct 28 '13 at 23:49
1

Don't know what C89 said about that, @David天宇Wong, that (the usual arithmetic conversions) - in principle - might have been there too. Of course `uint64_t` wasn't, that's since C99. – Daniel Fischer Oct 29 '13 at 00:54

score 3 · Answer 2 · answered Sep 18 '12 at 19:43

This may be a bit naive, but I'd loop from 0 to 63, clear the relevant bit, and see if the result is 0:

if (b != 0) {
    for (i = 0; i < 64; ++i) {
        if (b & ~(1 << i)) == 0) {
            return 1;
        }
    }
    return 0;
}

it's nowhere near as clever as the other posted answers, but it has the advantage of being easy to understand.

Test if a bitboard have only one bit set to 1

2 Answers2