Использование логического И/ИЛИ без условного/ветвления

Я пытаюсь написать функцию, которая подсчитывает некоторые битовые флаги, избегая использования ветвления или условий:

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

Нулевой бит напрямую не считается, а биты 1-4 учитываются только в том случае, если бит 0 не установлен, бит 5 считается безоговорочно, биты 6-7 могут считаться только один раз.

Однако я понимаю, что логические операторы && и || используйте оценку короткого замыкания. Это означает, что их использование создает условную ветвь, как вы могли бы видеть в таких примерах: if( ptr != nullptr && ptr->predicate()), которая гарантирует, что код во втором подвыражении не будет выполнен, если результат вычисляется по короткому замыканию из первого подвыражения.

Первая часть вопроса: нужно ли что-то делать? Поскольку это чисто арифметические операции без побочных эффектов, будет ли компилятор создавать условные переходы?

Вторая часть: я понимаю, что побитовые логические операторы не закорачивают оценку, но единственная проблема - биты не выстраиваются. Результат маскирования n-го бита равен либо 2^n, либо нулю.

Как лучше всего сделать такое выражение, как (n & 16), равным 1 или 0?


c++ boolean-logic bit-manipulation short-circuiting bitwise-operators
person stands2reason    schedule 21.11.2017    source источник
comment
В порядке. Значит, ты очень умный и умеешь делать умные вещи с помощью битов. Никто больше не будет иметь ни малейшего представления о том, что на самом деле должна делать ваша версия (даже если вы прокомментируете ее, комментарий в конечном итоге отойдет от кода. Так всегда и бывает). ремонтопригодный способ начать с?   -  person John3136    schedule 21.11.2017
comment
Apple LLVM 8.1.0 оптимизирует подпрограмму для кода без каких-либо ветвей (для цели по умолчанию в macOS). Однако это не то поведение, на которое можно положиться. Разные компиляторы будут делать разные вещи, и даже один компилятор может делать разные вещи в разных обстоятельствах. В основном вы должны писать четкий код и избегать вещей, которые скрывают, что происходит, ни для людей, ни для компилятора.   -  person Eric Postpischil    schedule 21.11.2017
comment
ответ для второй части: (n & x) << x даст вам 0 или 1 за x = 2^k   -  person kmdreko    schedule 21.11.2017
comment
Чтобы расширить мнение Эрика: современные компиляторы с включенной оптимизацией более чем достаточно умны, чтобы генерировать оптимальный код для таких функций. Избегать ветвей также не обязательно быстрее. Я бы просто написал эту функцию так, чтобы человек мог понять ее без особых усилий, и позволил бы компилятору творить чудеса.   -  person Filipp    schedule 21.11.2017

Ответы (3)


arrow_upward
1
arrow_downward

Я предполагаю, что «бит 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;

}
person Detonar    schedule 21.11.2017
comment
Мне любопытно, почему для таких операций, как эти, (n&1)*(n&4 >> 2), где логическое сравнение выполняется только с 0-м битом, умножение предпочтительнее побитового И? - person stands2reason; 14.12.2017
comment
@stands2reason Возможно, то же самое можно сделать с & вместо *, но мне так легче читать. - person Detonar; 15.12.2017

arrow_upward
1
arrow_downward

Как лучше всего сделать такое выражение, как (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)
person AShelly    schedule 15.12.2017

arrow_upward
0
arrow_downward

Я думаю, что самый чистый способ преобразовать (n & 16) в 0 или 1 — просто использовать int(bool(n & 16)). Приведение к int можно отбросить, если вы используете их в арифметическом выражении (например, bool(n & 2) + bool(n & 4)).
Для вашей функции подсчета набора битов я бы рекомендовал использовать встроенную функцию popcount, доступную как __builtin_popcount в gcc и __popcnt в MSVC. Ниже мое понимание функции, которую вы описали, изменено на использование 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

Это не совсем соответствует функции, которую вы написали, но, надеюсь, отсюда вы поняли идею.

person SirGuy    schedule 15.12.2017