Самый эффективный способ проверить, является ли положительное целое число 2^n (т.е. 1, 2, 4, 8 и т. д.) в C++20?

bool test = std::has_single_bit(n);

std::has_single_bit следует преобразовать в наиболее эффективную последовательность для текущей платформы.

template< class T >
constexpr bool has_single_bit( T x ) noexcept;

(начиная с С++20)

Проверяет, является ли x целой степенью двойки.

Эта перегрузка участвует в разрешении перегрузки, только если T является целочисленным типом без знака (то есть unsigned char, unsigned short, unsigned int, unsigned long, unsigned long long или расширенным целочисленным типом без знака).

Насколько читаемым вы хотите свой код?

   x = x - ((x >> 1) & 0x55555555);
   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
   x = (x + (x >> 4)) & 0x0F0F0F0F;
   x = x + (x >> 8);
   x = x + (x >> 16);
   if (x == 1) {
   }

Это алгоритм подсчета битов из «Hacker's Delight», старой сокровищницы полезных алгоритмов перебора битов.

   x = x - ((x >> 1) & 0x55555555);

выполняет попарное сложение битов. Обратите внимание, что

000 >>1 = 000, 000 & 101 = 0
001 >>1 = 000, 000 & 101 = 0
010 >>1 = 001, 001 & 101 = 1
011 >>1 = 001, 001 & 101 = 1
100 >>1 = 010, 010 & 101 = 0
101 >>1 = 010, 010 & 101 = 0
110 >>1 = 011, 011 & 101 = 1
111 >>1 = 011, 011 & 101 = 1

Таким образом, ((x >> 1) & 0x555555555) действует как «набор 2» каждых двух битов по порядку внутри слова.

Это означает, что при вычитании результата вычитается 1, если 2 установлено в каждой паре, или ничего не вычитается, если оно не установлено. В каждой паре битов теперь есть счетчик этой пары, хранящийся там, где эта пара была раньше.

Остальные строки затем выполняют попарное суммирование, складывая счетчики каждой пары «2 бит», суммируя счетчики каждой пары «4 бита», суммируя счетчик каждой пары «8 бит» и так далее. Если вам нужно сделать два 64-битных слова, вы можете добавить дополнительную строку.

Наконец, чтобы проверить, установлен ли у вас один бит, вы проверяете, равен ли счетчик 1.

Обратите внимание: хотя это и интересно рассматривать, лучше использовать std::has_single_bit, который использует тот же алгоритм (но параметризован для обработки слов разной длины и проверяет, что количество битов (алгоритм, о котором я говорю) равно 1. Приведенное выше решение предназначено для 32-битных слов, но его можно легко изменить для 64-битных слов.

https://github.com/gcc-mirror/gcc/blob/bd3a312728fbf8c35a09239b9180269f938f872e/libstdc%2B%2B-v3/include/std/bit#L325

Хакерский восторг https://learning.oreilly.com/library/view/hackers-delight- Second/9780133084993/

Вы знаете, что ваше число положительное (что исключает ноль), поэтому вы действительно можете просто использовать n & (n-1) == 0, не проверяя n != 0. Это ваш самый эффективный вариант, потенциально более эффективный, чем C++20 std::has_single_bit

std::has_single_bit необходимо исключить случай отсутствия набора битов. Для этого на современном x86 может быть немного эффективнее сделать popcount(n) == 1, если компилятор может предположить поддержку аппаратной popcnt инструкции, поэтому std::has_single_bit часто определяется именно так в стандартных библиотеках C++.

Но поскольку вы знаете, что ваше число не равно нулю, битхак наиболее эффективен. Особенно при компиляции для цели, где компилятор не может принять аппаратный popcount (например, x86 без -march=x86-64-v2 или новее) или AArch64 до ARMv9.x, где скалярный popcount требует копирования в векторные регистры и обратно. RISC-V имеет аппаратный счетчик всплывающих окон только в необычном расширении, а не в базовой версии.

На x86 это может быть так же дешево, как

  lea   eax, [rdi-1]
  test  eax, edi
   # boolean condition in ZF
  jz  or setz  or cmovz  or whatever

И аналогично AArch64 с sub и tst. И практически любой другой современный RISC может вычесть 1, помещая результат в отдельный регистр, а затем дешево И все вместе.

А если вы компилируете для -march=x86-64-v3 или более поздней версии (BMI2 + AVX2 + FMA = набор функций Haswell), компилятор может использовать BMI1 blsr eax, edi для очистки («сброса») младшего установленного бита и установки ФЛАГОВ соответственно, с ZF, установленным в соответствии с нулевым выходным сигналом. CF устанавливается, если входной сигнал равен нулю, поэтому некоторые условия ветвления могут это проверить n!=0. Но, к сожалению, такие условия, как jbe есть CF=1 or ZF=1, ja есть CF=0 and ZF=0. Не существует ни одного условия FLAGS, проверяющего ZF=1 и CF=0, которое позволило бы std::has_single_bit скомпилировать только blsr плюс одну ветку, cmov или setcc. ja берется, если на входе установлено несколько битов, не принимается для степени 2 или нуля.

В отличие от test, blsr не может объединяться макросом с более поздним jcc, поэтому он не сохраняет никаких ошибок по сравнению с lea/test, если вы разветвляете его. В Intel лучше, если компилятор будет использовать его независимо, например, для setnz или cmovnz. blsr — это одиночный процессор на Intel, AMD Zen 4 и более поздних версиях. 2 уопа на Zen 3 и более ранних версиях (https://uops.info/)

Непопсовый способ исключить ноль

Для случаев использования, когда вы не можете принять ненулевой ввод и не имеете дешевого аппаратного popcount, существует альтернативный битхак, который состоит из 3 операций вместо двух: (n - 1) < (n ^ (n - 1))

Правая часть — это то, что вычисляет x86 BMI1 blsmsk, но если у нас есть blsmsk, то у нас есть popcnt.
n-1 — это распространенное подвыражение, поэтому нам нужно вычислить его только один раз. Например RISC-V; AArch64 может быть похож на cmp/bltu.

 addi  x1, x0, -1             # n-1
 xor   x2, x1, x0             # n ^ (n-1)
 bltu  x1, x2, power_of_two   # branch on a comparison

Для нуля n-1 — это UINT_MAX, а n ^ anything — неактивный оператор, поэтому обе стороны равны.

Для степени двойки n-1 устанавливает все биты ниже того места, где был установленный бит, и XOR устанавливает этот бит снова. Итак, оно больше, чем n, а также больше, чем n-1.

Для числа, не являющегося степенью двойки, n ^ (n-1) по-прежнему является просто маской до самого младшего установленного бита включительно, при этом старшие биты отменены (те, которые n-1 не перевернулись). Значит, он меньше n-1.

https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 также предлагает v && !(v & (v - 1));, но я не думаю, что это лучше, поскольку логическое && должно проверять обе стороны на ненулевое значение.