CODEWITHSUNDEEP
c++bit-manipulationbitwise-operatorsboolean-logicshort-circuiting
stands2reason
stands2reason

Reputation: 730

Use of logical AND/OR without conditional/branching

I am trying to write a function that counts some bit flags while avoiding the use of branching or conditionals:

uint8_t count_descriptors(uint8_t n)
{
    return 
    ((n & 2)   && !(n & 1))   +
    ((n & 4)   && !(n & 1))   +
    ((n & 8)   && !(n & 1))   +
    ((n & 16)  && !(n & 1))   +
    ((n & 32)  && 1       )   +
    ((n & 64)  || (n & 128))  ;
}

Bit zero is not directly counted, but bits 1-4 are only considered if bit 0 is not set, bit 5 is considered unconditionally, bit 6-7 can only counted once.

However, I understand that the boolean && and || use short-circuit evaluation. This means that their use creates a conditional branch, as you would see in such examples: if( ptr != nullptr && ptr->predicate()) that guarantees code in the second sub-expression is not executed if the result is short-circuit evaluated from the first sub-expression.

The first part of the question: do I need to do anything? Since these are purely arithmetic operations with no side-effects, will the compiler create conditional branches?

Second part: I understand that bitwise boolean operators do not short-circuit evaluate, but the only problem the bits do not line up. The result of masking the nth bit is either 2^n or zero.

What is the best way to make an expression such as (n & 16) evaluate to 1 or 0?

Upvotes: 1

Views: 985

Answers (3)

AShelly
AShelly

Reputation: 35540

What is the best way to make an expression such as (n & 16) evaluate to 1 or 0?

By shifting it right the required number of bits: either (n>>4)&1 or (n&16)>>4.

I'd probably use a lookup table, either for all 256 values, or at least for the group of 4.

nbits[16]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
//count bits 1..4 iff bit 0 is 0, bit 5 always, and bit 6 or 7
return (!(n&1) * nbits[(n>>1)&0xF]) + ((n>>5)&1) + (((n>>6)|(n>>7))&1)

Upvotes: 1

SirGuy
SirGuy

Reputation: 10770

I think the cleanest way to convert (n & 16) into 0 or 1 is to just use int(bool(n & 16)). The cast to int can be dropped if you are using them in an arithmetic expression (like bool(n & 2) + bool(n & 4)).
For your function of counting bits set I would recommend using the popcount intrinsic function, available as __builtin_popcount on gcc and __popcnt on MSVC. Below is my understanding of the function you described, changed to use popcount.

f(n & 1)
{
  //clear out first 4 bits and anything > 255
  n &= 0xF0;
}
else
{
  //clear out anything > 255 and bottom bit is already clear
  n &= 0xFF;
}

return __builtin_popcount(n); //intrinsic function to count the set bits in a number

This doesn't quite match the function you wrote, but hopefully from here you get the idea.

Upvotes: 0

Detonar
Detonar

Reputation: 1429

I assume with "bit 6-7 can only counted once" you mean only one of them is being counted

In this case something like this should work

uint8_t count_descriptors(uint8_t n)
{
    uint8_t retVar;

    retVar = (n&1)*(n&2 >> 1) + 
             (n&1)*(n&4 >> 2) + 
             (n&1)*(n&8 >> 3) +
             (n&1)*(n&16 >> 4) + 
             (n&32 >> 5) + 
             (int)((n&64 >> 6) + (n&128 >> 7) >= 1)

    return retVar;

}

Upvotes: 1

Related Questions