Test if a bitboard have only one bit set to 1 [duplicate]

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

Ruthenium

Answer 1

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.

Aristophanes

ah, the old "is power of two" algoritm – Seif

Thanks very much! and can you tell me how to test if all 1 bits are in odd or even positions? – Ruthenium

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

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. – Aristophanes

Daniel seems to agree, so give it ago :-) – Seif

Why not just if (b == 0xAAAA...) and if (b == 0x5555...) if we know the type of b? – Hephzibah

@Hephzibah 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. – Aristophanes

@DanielFischer my bad, I think I misunderstood the question. – Hephzibah

Aren't you supposed to write (b - (bboard) 1) ? otherwise 1 could be in 32 bits. – Barri

@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. – Aristophanes

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. – Aristophanes

Answer 2

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.

Autonomy