Каков эффективный способ подсчета установленных битов в позиции или ниже?

Question

Каков эффективный способ подсчета установленных битов в позиции или ниже?

Дано std::bitset<64> bits с любым количеством установленных битов и позицией битов X (0-63)

Каков наиболее эффективный способ подсчета битов в позиции X или ниже или возврата 0, если бит в X не установлен

Примечание: если бит установлен, возврат всегда будет по крайней мере 1

Путь грубой силы очень медленный:

int countupto(std::bitset<64> bits, int X)
{
  if (!bits[X]) return 0;
  int total=1;
  for (int i=0; i < X; ++i)
  {
    total+=bits[i];
  }
  return total;
}

count() Метоф из bitset даст вам popcount из всех битов, но bitset не поддерживает диапазоны

Примечание: это не дубликат Как подсчитать количество установленных бит в 32-битном целом числе? так как это спрашивает обо всех битах не в диапазоне от 0 до X

37

c++ algorithm performance bit-manipulation

Источник

user2963099 22 дек '15 в 02:09

5 ответов

Решение

Моя немедленная реакция - проверить указанный бит и сразу же вернуть 0, если он чист.

Если вы пройдете мимо этого, создайте битовую маску с установленным битом (и менее значимыми), и and что с оригинальным входом. Затем используйте count() функция-член, чтобы получить количество битов, установленных в результате.

Что касается создания маски: вы можете сместить 1 влево на N мест, затем вычесть 1.

10

Источник

user179910 22 дек '15 в 02:13

Предполагая unsigned long или же unsigned long long достаточно большой, чтобы вместить 64 бита, вы можете позвонить bits.to_unlong() (или же bits.to_ullong()) чтобы получить данные набора битов как целое число, замаскируйте биты выше X ((1 << X) - 1) затем посчитайте эти биты, как указано в ответе на вопрос, на который вы ссылаетесь.

5

Источник

user5231607 22 дек '15 в 02:16

Легко конвертировать между битом и маской для битов под ним, поэтому что-то вроде этого должно работать:

int popcnt(bitset<64> bs, int x) {
    // Early out when bit not set
    if (!bs[x]) return 0;
    // Otherwise, make mask from `x`, mask and count bits
    return (bs & bitset<64>((1UL << x) - 1)).count() + 1;
}

Здесь предполагается, что bitset::count реализовано эффективно (используя popcnt внутренняя или эффективный запасной вариант); это не гарантируется, но люди из STL стремятся оптимизировать подобные вещи.

5

Источник

user364696 22 дек '15 в 02:16

Я отредактировал проблему, которую я видел прежде, которая проверила бы, установлено ли нечетное или четное число битов в числе. Это для C, но не должно быть слишком сложно втиснуть его в C++. Суть решения в том, что находится в цикле. Попробуйте это на бумаге, чтобы понять, как он выбирает LSB, а затем удаляет его из x. Остальная часть кода проста. Код выполняется в O(n), где n - количество битов в x. Это намного лучше, чем линейное время, которое я тоже считал возможным только при первом взгляде на эту проблему.

#include <stdio.h>

int
count(long x, int pos)
{
    /* if bit at location pos is not set, return 0 */
    if (!((x >> pos) & 1))
    {
        return 0;
    }

    /* prepare x by removing set bits after position pos */
    long tmp = x;
    tmp = tmp >> (pos + 1);
    tmp = tmp << (pos + 1);
    x ^= tmp;

    /* increment count every time the first set bit of x is removed (from the right) */
    int y;
    int count = 0;
    while (x != 0)
    {
        y = x & ~(x - 1);
        x ^= y;
        count++;
    }
    return count;
}

int
main(void)
{
    /* run tests */
    long num = 0b1010111;
    printf("%d\n", count(num, 0)); /* prints: 1 */
    printf("%d\n", count(num, 1)); /* prints: 2 */
    printf("%d\n", count(num, 2)); /* prints: 3 */
    printf("%d\n", count(num, 3)); /* prints: 0 */
    printf("%d\n", count(num, 4)); /* prints: 4 */
    printf("%d\n", count(num, 5)); /* prints: 0 */
    printf("%d\n", count(num, 6)); /* prints: 5 */
}

1

Источник

user1812249 22 дек '15 в 06:36

Другие вопросы по тегам c++ algorithm performance bit-manipulation

user224132 22 дек '15 в 07:15 2015-12-22 07:15 · Accepted Answer · 2015-12-22 07:15

Этот C++ заставляет g++ испускать очень хороший x86 ASM (проводник компилятора Godbolt). Я ожидаю, что он будет эффективно компилироваться и на других 64-битных архитектурах (если есть HW popcount для std::bitset::count использовать, иначе это всегда будет медленной частью):

#include <bitset>

int popcount_subset(std::bitset<64> A, int pos) {
  int high_bits_to_eliminate = 63 - pos;
  A <<= (high_bits_to_eliminate & 63);  // puts A[pos] at A[63].

  return (A[63]? ~0ULL : 0) & A.count();  // most efficient way: great code with gcc and clang
  // see the godbolt link for some #ifdefs with other ways to do the check, like
    // return A[BSET_SIZE-1] ? A.count() : 0;
}

Это, вероятно, не оптимально для 32-битных архитектур, поэтому сравните другие альтернативы, если вам нужно сделать 32-битную сборку.

Это будет работать для битов других размеров, если вы что-то делаете с жестко закодированным 63 и изменить & 63 маска для подсчета сдвига в более общую проверку диапазона. Для оптимальной производительности с битовыми наборами странного размера создайте шаблонную функцию со специализацией для size <= register width целевой машины. В этом случае извлеките набор битов в unsigned введите соответствующую ширину и сдвиньте верхнюю часть регистра вместо верхней части набора битов.

Вы ожидаете, что это также сгенерирует идеальный код для bitset<32>, но это не совсем. gcc/clang по-прежнему использует 64-битные регистры на x86-64.

Для больших наборов битов сдвиг всего будет медленнее, чем просто пересчет слов ниже того, который содержит pos и используя это в этом слове. (Вот где векторизованный попконт действительно светит на x86, если вы можете предполагать SSSE3, но не popcnt поддержка оборудования insn, или для 32-битных целей. AVX2 256bit pshufb это самый быстрый способ сделать массовые поп-аккаунты, но без AVX2 я думаю, что 64bit popcnt довольно близко к 128-битному pshufb реализация. Смотрите комментарии для дальнейшего обсуждения.)

Если у вас есть массив 64-битных элементов, и вы хотите считать биты ниже определенной позиции в каждом из них по отдельности, то вам определенно следует использовать SIMD. Сдвиговые части этого алгоритма векторизованы, а не только часть popcnt. использование psadbw от регистра с нулем до байтов с горизонтальной суммой в 64-битных порциях после pshufb основанный на popcnt, который производит счетчики для битов в каждом байте отдельно. SSE/AVX не имеет 64-битного арифметического сдвига вправо, но вы можете использовать другую технику для смешивания старшего бита каждого элемента.

Как я придумал это:

Инструкции asm, которые вы хотите получить для вывода компилятора, будут:

удалить ненужные биты из 64-битного значения
проверить самый высокий из разыскиваемых бит.
попконт это.
вернуть 0 или popcount, в зависимости от результата теста. (Обе реализации без ветвей или ветвления имеют свои преимущества. Если ветвление предсказуемо, реализация без ветвей имеет тенденцию быть медленнее.)

Очевидный способ сделать 1 состоит в том, чтобы сгенерировать маску ((1<<(pos+1)) -1) а также & Это. Более эффективный способ - сдвиг влево на 63-pos оставив нужные биты в верхней части регистра.

Это также имеет интересный побочный эффект, заключающийся в размещении бита, который вы хотите проверить, в качестве верхнего бита в регистре. Тестирование знакового бита, а не любого другого произвольного бита, занимает немного меньше инструкций. Арифметическое смещение вправо может транслировать бит знака на остальную часть регистра, что позволяет использовать код без ответвлений более эффективно, чем обычно.

Работа с поп-счетом - очень обсуждаемая проблема, но на самом деле это более сложная часть головоломки. На x86 это чрезвычайно эффективная аппаратная поддержка, но только на достаточно недавнем оборудовании. На процессорах Intel popcnt Инструкция доступна только на Nehalem и новее. Я забыл, когда AMD добавила поддержку.

Таким образом, чтобы использовать его безопасно, вам нужно либо выполнить диспетчеризацию процессора с резервным, который не использует popcnt, Или создайте отдельные двоичные файлы, которые не зависят от некоторых функций процессора.

попконт без popcnt Инструкция может быть выполнена несколькими способами. Один использует SSSE3 pshufb реализовать 4-битную LUT. Это наиболее эффективно при использовании всего массива, а не одного 64b за раз. Скалярные битхаки здесь могут быть лучшими и не требуют SSSE3 (и поэтому будут совместимы с древними процессорами AMD, которые имеют 64-битные, но не pshufb.)

Бит-трансляция:

(A[63]? ~0ULL : 0) просит компилятор передать старший бит всем остальным битовым позициям, позволяя использовать его как маску AND для обнуления (или нет) результата popcount. Обратите внимание, что даже для больших размеров битов он все еще только маскирует вывод popcnt не сам битсет, так ~0ULL Хорошо, я использовал ULL, чтобы убедиться, что никогда не просил компилятор транслировать бит только на младшие 32 бита регистра (с UL в Windows, например).

Эта трансляция может быть выполнена с арифметическим смещением вправо на 63, которое смещается в копиях старшего бита.

Clang сгенерировал этот код из оригинальной версии. После некоторых слов от Гленна о различных реализациях для 4, я понял, что могу привести gcc к оптимальному решению clang, написав исходный код, более похожий на тот, который я хочу. Очевидное ((int64_t)something) >> 63 более непосредственный запрос арифметического сдвига вправо не будет строго переносимым, поскольку знаковые сдвиги вправо определяются реализацией как арифметического или логического. Стандарт не предусматривает переносимого арифметического оператора правого сдвига. (Это не неопределенное поведение, однако.) В любом случае, к счастью, компиляторы достаточно умны: gcc видит лучший способ, как только вы дадите ему достаточно подсказки.

Этот источник делает отличный код на x86-64 и ARM64 с gcc и clang. Оба просто используют арифметическое смещение вправо на входе для popcnt (поэтому сдвиг может выполняться параллельно с popcnt). Он также отлично компилируется на 32-битной x86 с gcc, потому что маскирование происходит только с 32-битной переменной (после добавления нескольких результатов popcnt). Это остальная часть функции, которая неприятна на 32-битной (когда битовый набор больше, чем регистр).

Оригинальная троичная версия оператора с gcc

Скомпилировано с gcc 5.3.0 -O3 -march=nehalem -mtune=haswell (более старый gcc, как 4.9.2, также по-прежнему выдает это):

; the original ternary-operator version.  See below for the optimal version we can coax gcc into emitting.
popcount_subset(std::bitset<64ul>, int):
    ; input bitset in rdi, input count in esi (SysV ABI)
    mov     ecx, esi    ; x86 variable-count shift requires the count in cl
    xor     edx, edx    ; edx=0 
    xor     eax, eax    ; gcc's workaround for popcnt's false dependency on the old value of dest, on Intel
    not     ecx         ; two's complement bithack for 63-pos (in the low bits of the register)
    sal     rdi, cl     ; rdi << ((63-pos) & 63);  same insn as shl (arithmetic == logical left shift)
    popcnt  rdx, rdi
    test    rdi, rdi    ; sets SF if the high bit is set.
    cmovs   rax, rdx    ; conditional-move on the sign flag
    ret

См. Как доказать, что оператор C -x, ~x+1 и ~(x-1) дают одинаковые результаты? для фона на использование GCC из -x == ~x + 1 два дополнения идентичности. (И какие целочисленные операции дополнения 2 можно использовать без обнуления старших битов на входах, если требуется только младшая часть результата? Который косвенно упоминает, что shl маскирует счетчик сдвига, поэтому нам нужны только младшие 6 бит ecx держать 63 - pos, Главным образом связывая это, потому что я написал это недавно, и любой, кто все еще читает этот параграф, может найти это интересным.)

Некоторые из этих инструкций пропадут при вставке. (например, gcc сначала сгенерирует счет в ecx.)

С умножением Гленна вместо тернарного оператора USE_mul), gcc делает

    shr     rdi, 63
    imul    eax, edi

в конце вместо xor / test / cmovs,

Анализ Haswell , используя данные микроархива от Agner Fog (Multiply version):

mov r,r: 1 UOP с плавким доменом, 0 задержек, без исполнительного устройства
xor обнуление: 1 UOP с плавким доменом, без исполнительного устройства
not: 1 моп для p0/p1/p5/p6, задержка 1с, 1 на пропускную способность 0, 25с
shl (ака sal) с учетом в cl:3 моп для p0/p6: задержка 2c, 1 на пропускную способность 2c. (Данные Agner Fog указывают на то, что IvyBridge требует всего 2 моп для этого, как ни странно.)
popcnt: 1 моп для задержки p1, 3c, 1 на 1c пропускной способности
shr r,imm: 1 моп для p0/p6, латентность 1с. 1 на 0,5c пропускной способности.
imul r,r: 1 моп для задержки p1, 3c.
не считая ret

Итоговые:

9 мопов слитых доменов могут выдавать за 2, 25 циклов (теоретически; эффекты мегапиксельной строки кэша обычно являются узким местом для внешнего интерфейса).
4 моп (сдвиги) для p0/p6. 2 моп для р1. 1 любой-ALU-порт моп. Может выполняться по одному на 2c (насыщение портов сдвига), поэтому внешний интерфейс является худшим узким местом.

Задержка: критический путь от момента, когда набор битов готов к моменту, когда результат: shl (2) -> popcnt (3) -> imul (3). Всего 8 циклов. Или 9с с когда pos готов, потому что not это дополнительная задержка 1с для него.

Оптимальный bitbroadcast версия заменяет shr с sar (тот же перф) и imul с and (Задержка 1с вместо 3с работает на любом порту). Таким образом, единственное изменение перфорации - это уменьшение задержки критического пути до 6 циклов. Пропускная способность все еще остается узким местом на фронтенде. and возможность работать на любом порту не имеет значения, если только вы не смешиваете это с кодом, который является узким местом на порту 1 (вместо того, чтобы смотреть на пропускную способность для выполнения только этого кода в узком цикле).

cmov (троичный оператор) версия: 11 мопов слитых доменов (внешний интерфейс: один на 2.75c). исполнительные блоки: все еще узкое место на портах смены (p0/p6) по одному на 2c. Задержка: 7c от набора битов к результату, 8c от pos к результату. (cmov задержка 2c, 2 моп для любого из p0/p1/p5/p6.)

У Clang есть несколько разных хитростей: вместо test / cmovs, он генерирует маску из всех единиц или всех нулей, используя арифметическое смещение вправо, чтобы транслировать бит знака на все позиции регистра. Я люблю это: Использование and вместо cmov более эффективно на Intel. Он все еще имеет зависимость от данных и выполняет работу для обеих сторон ветви (что является основным недостатком cmov в целом). Обновление: с правильным исходным кодом, gcc также будет использовать этот метод.

лязг 3.7 -O3 -Wall -march=nehalem -mtune=haswell

popcount_subset(std::bitset<64ul>, int):
    mov     ecx, 63
    sub     ecx, esi      ; larger code size, but faster on CPUs without mov-elimination
    shl     rdi, cl       ; rdi << ((63-pos) & 63)
    popcnt  rax, rdi      ; doesn't start a fresh dep chain before this, like gcc does
    sar     rdi, 63       ; broadcast the sign bit
    and     eax, edi      ; eax = 0 or its previous value
    ret

sar / and заменяет xor / test / cmov, а также cmov это 2-х ступенчатая инструкция для процессоров Intel, так что это действительно хорошо. (Для троичной версии оператора).

Clang по-прежнему делает sar / and трюк вместо фактического imul при использовании многократной исходной версии или исходной версии "bitbroadcast". Таким образом, они помогают GCC, не повреждая лязг. (sar/and определенно лучше чем shr/imul: 2c меньше задержки на критическом пути.) pow_of_two_sub версия действительно причиняет боль лягушатнику (см. первую ссылку на Годболт: в этом ответе пропущено, чтобы избежать беспорядка с идеями, которые не оправдались).

mov ecx, 63 / sub ecx, esi на самом деле быстрее на процессорах без устранения mov для reg,reg move (нулевая задержка и отсутствие порта выполнения, обрабатывается переименованием регистра). Это включает в себя Intel до IvyBridge, но не более новые процессоры Intel и AMD.

Clang-х mov imm / sub метод ставит только один цикл задержки для pos на критический путь (за пределами задержки bitset->result) вместо двух для mov ecx, esi / not ecx на процессорах где mov r,r имеет задержку 1с.

С BMI2 (Haswell и позже), оптимальная версия ASM может сохранить mov в ecx, Все остальное работает так же, потому что shlx маскирует свой входной регистр счетчика сдвига до размера операнда, как shl,

Команды сдвига x86 имеют сумасшедшую семантику CISC, где, если счетчик сдвига равен нулю, флаги не затрагиваются. Таким образом, инструкции сдвига с переменным счетом имеют (потенциальную) зависимость от старого значения флагов. "Нормальный" x86 shl r, cl декодирует до 3 мопов на Haswell, но BMI2 shlx r, r, r только 1. Так что очень плохо, что gcc по-прежнему излучает sal с -march=haswell, Вместо того, чтобы использовать shlx (который он использует в некоторых других случаях).

// hand-tuned BMI2 version using the NOT trick and the bitbroadcast
popcount_subset(std::bitset<64ul>, int):
    not     esi           ; The low 6 bits hold 63-pos.  gcc's two-s complement trick
    xor     eax, eax      ; break false dependency on Intel.  maybe not needed when inlined.
    shlx    rdi, rdi, rsi ; rdi << ((63-pos) & 63)
    popcnt  rax, rdi
    sar     rdi, 63       ; broadcast the sign bit: rdi=0 or -1
    and     eax, edi      ; eax = 0 or its previous value
    ret

Анализ производительности для Intel Haswell: 6 мопов с плавкими доменами (внешний интерфейс: один на 1.5c). Единицы исполнения: 2 p0/p6 смена мопов. 1 р1 моп. 2 any-port uops: (один на 1.25c от общего ограничения порта выполнения). Задержка критического пути: shlx (1) -> popcnt (3) -> and (1) = 5c bitset-> результат. (или 6с из pos -> результат).

Обратите внимание, что при встраивании человек (или умный компилятор) мог бы избежать необходимости xor eax, eax, Это только из-за popcnt ложная зависимость от выходного регистра (на Intel), и нам нужен выход в eax (который вызывающий абонент, возможно, использовал недавно для длинной цепочки депов). С -mtune=bdver2 или что-то, GCC не обнулит регистр, который он собирается использовать для popcnt выход.

При встраивании мы могли бы использовать выходной регистр, который уже должен быть готов по крайней мере уже popcnt Источник Reg, чтобы избежать проблемы. Компиляторы сделают на месте popcnt rdi,rdi когда источник не нужен позже, но это не тот случай. Вместо этого мы можем выбрать другой регистр, который уже должен быть готов перед источником. popcnt вход зависит от 63-pos, и мы можем заглушить это, так popcnt rsi,rdi зависимость от rsi не может задержать это. Или если бы мы имели 63 в регистре мы могли popcnt rsi,rdi / sarx rax, rsi, reg_63 / and eax, esi, Или команды сдвига BMI2 с 3 операндами также позволили бы нам не вводить вводные данные в случае, если они понадобятся впоследствии.

Это настолько легко, что издержки цикла и настройка входных операндов / сохранение результатов будут основными факторами. (И 63-pos можно оптимизировать с помощью константы времени компиляции или туда, откуда берется переменная count.)

Компилятор Intel забавно выстреливает себе в ногу и не использует тот факт, что A[63] является знаковым битом. shl / bt rdi, 63 / jc, Это даже настраивает ветви действительно тупым способом. Он может обнулить eax, а затем перепрыгнуть через popcnt или нет, основываясь на флаге, установленном shl,

Оптимальная реализация ветвления, начиная с вывода ICC13 из -O3 -march=corei7 на кресте:

   // hand-tuned, not compiler output
        mov       ecx, esi    ; ICC uses neg/add/mov :/
        not       ecx
        xor       eax, eax    ; breaks the false dep, or is the return value in the taken-branch case
        shl       rdi, cl
        jns    .bit_not_set
        popcnt    rax, rdi
.bit_not_set:
        ret

Это в значительной степени оптимально: A[pos] == true дело имеет одну не занятую ветку. Это не сильно экономит по сравнению с методом без ветвей.

Если A[pos] == false случай более распространен: перепрыгнуть через ret инструкция, чтобы popcnt / ret, (Или после вставки: перейти к блоку в конце, который делает popcnt и прыгает назад).