Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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

For example if n = 3 I only care about the 3 least significant bits 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 to 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.

like image 342
Mathieu Pagé Avatar asked Feb 08 '15 04:02

Mathieu Pagé


2 Answers

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);
}
like image 99
Barry Avatar answered Sep 29 '22 07:09

Barry


How about?

int mask = (1<<n)-1;
if ((x&mask)==mask || (x&mask)==0) { /*do whatever*/ }

The only really tricky part is the calculation of the mask. It basically just shifts a 1 over to get 0b0...0100...0 and then subtracts one to make it 0b0...0011...1.

Maybe you can clarify what you wanted for the test?

like image 41
imallett Avatar answered Sep 29 '22 07:09

imallett