Is there an elegant and fast way to test for the 1-bits in an integer to be in a contiguous region?

Solution 1:

Solution:

static _Bool IsCompact(unsigned x)
{
    return (x & x + (x & -x)) == 0;
}

Briefly:

x & -x gives the lowest bit set in x (or zero if x is zero).

x + (x & -x) converts the lowest string of consecutive 1s to a single 1 higher up (or wraps to zero).

x & x + (x & -x) clears those 1 bits.

(x & x + (x & -x)) == 0 tests whether any other 1 bits remain.

Longer:

-x equals ~x+1 (for the int in the question, we assume two’s complement, but unsigned is preferable). After the bits are flipped in ~x, adding 1 carries so that it flips back the low 1 bits in ~x and the first 0 bit but then stops. Thus, the low bits of -x up to and including its first 1 are the same as the low bits of x, but all higher bits are flipped. (Example: ~10011100 gives 01100011, and adding 1 gives 01100100, so the low 100 are the same, but the high 10011 are flipped to 01100.) Then x & -x gives us the only bit that is 1 in both, which is that lowest 1 bit (00000100). (If x is zero, x & -x is zero.)

Adding this to x causes a carry through all the consecutive 1s, changing them to 0s. It will leave a 1 at the next higher 0 bit (or carry through the high end, leaving a wrapped total of zero) (10100000.)

When this is ANDed with x, there are 0s in the places where the 1s were changed to 0s (and also where the carry changed a 0 to a 1). So the result is not zero only if there is another 1 bit higher up.

Solution 2:

There is actually no need to use any intrinsics.

First flip all the 0s before the first 1. Then test if the new value is a mersenne number. In this algo, zero is mapped to true.

bool has_compact_bits( unsigned const x )
{
    // fill up the low order zeroes
    unsigned const y = x | ( x - 1 );
    // test if the 1's is one solid block
    return not ( y & ( y + 1 ) );
}

Of course, if you want to use intrinsics, here is the popcount method:

bool has_compact_bits( unsigned const x )
{
    size_t const num_bits = CHAR_BIT * sizeof(unsigned);
    size_t const sum = __builtin_ctz(x) + __builtin_popcount(x) + __builtin_clz(z);
    return sum == num_bits;
}