Строительным блоком для этого будет: добавление 1 к младшему биту смежной группы очистит все эти биты с выносом, оставив 1 бит установленным над группой.например, 0xff + 1 = 0x100 .
Если какие-либо биты не установлены, перенос не будет распространяться до конца, например, 0b01101 + 1 = 0b01110, а не установка бита # 4.(И если оставить некоторые из существующих битов установленными, то x & (x+1) будет истинным.)
Это работает для битовых групп в нижней части регистра (добавление 1) или в любой более высокой позиции(выделите младший установленный бит с помощью (-x) & x и добавьте его, например, с помощью BMI1 blsi или mov / neg / and).
Связанный битхак - это тест y & (y-1) дляцелое число, имеющее только один установленный бит (путем очистки самого младшего установленного бита): https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2. Но поскольку мы производим y с x+1, мы можем оптимизировать его до x & (x+1), чтобы обнаружитьнепрерывная маска внизу регистра.
Ваш конкретный случай очень прост:
- нижняя часть битового диапазона должна быть битом 0
- битовый диапазон в точности равен
n битам (длина префикса)
Эти ограничения означают, что есть ровно 1 целое число, которое соответствует обоим требованиям , поэтому вы должны предварительно- вычислите его и просто сравните на равенство с cmp/je.Число с n битами, установленными внизу, равно prefix_mask = (1<<n) - 1.Перенос (заимствование) путем вычитания устанавливает все биты ниже этого старшего разряда и очищает исходный бит.Биты выше этого значения остаются неустановленными, потому что этот старший бит удовлетворяет заимствованию.
Учитывая длину префикса n, вы можете вычислить 1<<n, используя bts (что является однопроцессным в IntelПроцессоры, или 2 мопа для AMD, https://agner.org/optimize/).
;; input: prefix length in EDX
;; output: prefix mask in ESI
xor esi, esi
bts esi, edx ; set bit n; eax |= 1<<n
dec esi ; set all the bits BELOW that power of 2
; then later, inside a loop: input in EAX
cmp eax, esi
je all_bits_set_up_to_prefix
@ fuz предложили LUT для этого, но это звучит как плохая идея, даже если вам приходится очень часто учитывать разные длины префиксов.Если не считать регистров, вы можете распределить их в стеке памяти после вычислений и использовать что-то вроде cmp [rsp+16], edx вместо статического LUT при циклическом преобразовании с той же длиной префикса.
Или выливать длину префикса в память, если вы этого не сделаетенужно некоторое время в регистре и просто сохранить маску.
Вы даже можете перевести маску обратно в длину префикса с помощью lea edx, [eax+1] / bsr edx,edx, чтобы найти битовый индекс самого высокого наборабит mask+1. (Или если возможна длина префикса 32, но ноль не возможен, то bsr / inc. BSR с input = 0 оставляет назначение неизменным и устанавливаетZF. AMD документирует это, говорят в документации Intel"undefined", но их текущее HW оставляет место назначения без изменений, поэтому инструкция имеет "ложную" зависимость от вывода.)
или без предварительного вычисления
Non-деструктивный тест EDX для всех младших битов n, а сам бит #n равен 0. (При добавлении 1 стираются младшие биты и устанавливается бит n , если это имело место).Вы можете использовать inc edx вместо LEA для копирования и добавления, если вы не используете его после.
;;; check the low n bits, ignoring whether higher bits are set or not
;;; inputs: prefix length in ECX, candidate in EDX
lea eax, [rdx+1]
bt eax, ecx
;;; output: CF = 1 if all the bits from 0..len-1 were set, else 0
Если вы также хотите исключить любые старшие битыпри установке вам потребуется еще одна инструкция, но это может быть инструкция test, которая будет сливаться с макросом jcc, поэтому на процессорах Intel это не требует дополнительных мопов.На процессорах AMD, где btr равен 2 мопам против bt, равному 1, это стоит 1 дополнительный моп.(test / jcc может объединиться в семействе AMD Bulldozer и более поздних версиях.)
;;; input: prefix length in ECX, candidate in EDX
lea eax, [rdx+1] ; produces a single set bit?
btr eax, ecx ; reset that bit, leaving eax=0 if no other bits were set
test eax, eax ; compare against zero
;;; output: ZF=1 (and eax=0) if EDX == (1<<ECX)-1 with no higher bits set.
jz contiguous_bitmask_of_length_ecx
Это стоит всего 3 мопа для Intel (4 для AMD), включая тестирование с макросом test / jz, дляветка на этом условии .И это не разрушает входной регистр.
Мы можем проверить наличие единой непрерывной группы битов неизвестной длины в нижней части регистра с помощью x & (x+1), чтообнаруживает, были ли установлены более высокие битыЕсли есть старший бит, который не перевернут переносом переноса, AND или TEST выдаст ненулевой результат.
Но это обрабатывает 0 и 1 так же, как многобитовые группыкак 0b0111.Возможно, вы захотите cmp eax, 3 / jb not_multibit_prefix до этого теста.
; check for a contiguous bit-group at the bottom of a reg of arbitrary length, including 0
;;; input: candidate in EDX
lea eax, [rdx+1] ; carry-out clears all the set bits at the bottom
test eax, edx ; set flags from x & (x+1)
;;; output: ZF=1 if the only set bits in EDX were a contiguous group at the bottom
Я посмотрел на странный взлом парциальных флагов lea eax, [rdx+1] / test eax, edx (ZF = 1: были установлены только смежные младшие биты) / bt eax, ecx (CF = 1: он закончился в той позиции, которую мы хотим). Но у x86 нет условия jcc , для которого требуется CF = 1 и ZF = 1. ja берется, если (CF=0 and ZF=0), jbe берется, если (CF=1 or ZF=1), поэтому ни один из них не работает. И, конечно, это было бы ужасно для процессоров без эффективного объединения частичных флагов, что приводило к остановке частичных флагов.
Общий случай: битгруппе не обязательно начинать снизу.
Это исключает простые предварительные вычисления.
Как упоминалось выше, мы можем выделить младший установленный бит с помощью (-x) & x. ИМТ1 добавил инструкцию для этого, blsi. Поэтому, если вы можете принять на себя поддержку BMI1, вы можете сделать это неразрушающим образом за 1 моп. В противном случае это займет 3.
unsigned bits_contiguous(unsigned x) {
unsigned lowest_set = (-x) & x; // isolate lowest set bit
unsigned add = x + lowest_set; // carry flips all the contiguous set bits
return (add & x) == 0; // did add+carry leave any bits un-flipped?
}
Я поместил это в проводник компилятора Godbolt, чтобы увидеть, заметил ли gcc или clang какие-либо оптимизации, о которых я не думал. Конечно, вы на самом деле не хотите материализовать целое число 0/1, как мы просим компилятор, но, поскольку они решили использовать test / setcc, мы можем просто посмотреть, что они делают, чтобы создать правильное состояние флага.
Мы можем написать несколько тестовых функций, чтобы убедиться, что логика верна для некоторых констант времени компиляции с #define TEST(n) int test##n(){return bits_contiguous(n);} (и посмотреть, является ли asm xor eax,eax или mov eax,1). См. C + asm в проводнике компилятора Godbolt . Некоторые интересные случаи TEST(0) = 1, потому что условие в основном проверяет наличие нескольких битовых групп. (Таким образом, для этой проверки нулевые битовые группы аналогичны 1-битной группе.) TEST(0xFFFFFFFF) = 1 также: наличие x+1 = 0 не является проблемой.
С gcc8.3 -O3 получаем
# gcc8.3 -O3 -march=haswell (enables BMI1 and BMI2)
bits_contiguous:
blsi eax, edi
add eax, edi
test eax, edi # x & (x+lowest_set)
sete al
movzx eax, al
ret
Без ИМТ1 нам нужно 3 инструкции вместо 1 для blsi:
mov eax, edi
neg eax
and eax, edi # eax = isolate_lowest(x)
add eax, edi
test eax, edi
Чтобы также проверить конкретную длину битовой группы, у @fuz была хорошая идея: popcnt, чтобы убедиться, что установлено правильное количество бит (и отдельно проверить, что они смежный). Popcnt не является базовой линией, у процессоров до Nehalem его нет и он выйдет из строя, если они попытаются запустить его.
;input: prefix len in ECX, candidate in EDX
;clobbers: EAX
popcnt eax, edx
cmp eax, ecx
jne wrong_number_of_bits_set ; skip the contiguousness test
blsi eax, edi
add eax, edi
test eax, edi # x & (x+lowest_set)
jz contiguous_bitgroup_of_length_ecx
wrong_number_of_bits_set: