使用不带条件/分支的逻辑AND/OR

Question

我正在尝试编写一个函数来计算一些位标志，同时避免使用分支或条件：

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))  ;
}

不直接计数位0，但仅考虑位1-4，如果位0未设置，则认为位5是无条件的，位6-7只能计数一次。

但是，我知道布尔值&&和||使用短路求值。这意味着使用它们会创建一个条件分支，就像您在这样的示例中看到的那样:如果从第一个子表达式计算的结果是短路，则保证第二个子表达式中的代码不会执行的if( ptr != nullptr && ptr->predicate())。

问题的第一部分:我需要做什么吗？由于这些都是没有副作用的纯算术操作，编译器会创建条件分支吗？

第二部分:我知道按位布尔运算符不会短路求值，但唯一的问题是位不对齐。掩码第n位的结果要么是2^n，要么是零。

使(n & 16)这样的表达式求值为1或0的最佳方法是什么？

Answer 1

我假设“比特6-7只能计数一次”，你的意思是它们中只有一个被计数

在这种情况下，像这样的东西应该可以工作

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;

}

Answer 2

让(n & 16)这样的表达式求值为1或0的最佳方法是什么？

将其向右移位所需的位数：(n>>4)&1或(n&16)>>4。

我可能会使用一个查找表，用于所有256个值，或者至少用于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)

Answer 3

我认为将(n & 16)转换为0或1最干净的方法就是使用int(bool(n & 16))。如果在算术表达式(如bool(n & 2) + bool(n & 4))中使用int，则可以删除对它们的强制转换。

对于计算位数集的函数，我建议使用popcount内部函数，在gcc上可以使用__builtin_popcount，在MSVC上可以使用__popcnt。下面是我对你所描述的函数的理解，改为使用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

这与您编写的函数并不完全匹配，但希望您能从这里得到概念。