How can I test if all bits are set or all bits are not?

Question

Using the bitwise operator how can I test if the n least significant bits of an integer are either all set or all not set.

For example if n = 3 I only care about the 3 least significant bits and the test should return true for 0 and 7 and false for all other values between 0 and 7.

Of course I could do if x = 0 or x = 7, but I would prefer something using bitwise operators.

Bonus points if the technique can be adapted to take into accounts all the bits defined by a mask.

Clarification :

If I wanted to test if bit one or two is set I could do if ((x & 1 != 0) && (x & 2 != 0)). But I could do the "more efficient" if ((x & 3) != 0).

I'm trying to find a "hack" like this to answer the question "Are all bits of x that match this mask all set or all unset?"

The easy way is if ((x & mask) == 0 || (x & mask) == mask). I'd like to find a way to do this in a single test without the || operator.

Answer 1

Using bitwise operator how can I test if the n least significant bits of an integer are either all sets or all not sets.

To get a mask for the last n significant bits, thats

(1ULL << n) - 1

So the simple test is:

bool test_all_or_none(uint64_t val, uint64_t n)
{
    uint64_t mask = (1ULL << n) - 1;
    val &= mask;
    return val == mask || val == 0;
}

If you want to avoid the ||, we'll have to take advantage of integer overflow. For the cases we want, after the &, val is either 0 or (let's say n == 8) 0xff. So val - 1 is either 0xffffffffffffffff or 0xfe. The failure causes are 1 thru 0xfe, which become 0 through 0xfd. Thus the success cases are call at least 0xfe, which is mask - 1:

bool test_all_or_none(uint64_t val, uint64_t n)
{
    uint64_t mask = (1ULL << n) - 1;
    val &= mask;
    return (val - 1) >= (mask - 1);
}

We can also test by adding 1 instead of subtracting 1, which is probably the best solution (here once we add one to val, val & mask should become either 0 or 1 for our success cases):

bool test_all_or_none(uint64_t val, uint64_t n)
{
    uint64_t mask = (1ULL << n) - 1;
    return ((val + 1) & mask) <= 1;
}     

For an arbitrary mask, the subtraction method works for the same reason that it worked for the specific mask case: the 0 flips to be the largest possible value:

bool test_all_or_none(uint64_t val, uint64_t mask)
{
    return ((val & mask) - 1) >= (mask - 1);
}