Какой алгоритм наиболее эффективен для достижения следующего:
0010 0000 => 0000 0100
Преобразование из MSB-> LSB в LSB-> MSB. Все биты должны быть обращены; то есть это не обмен байтов
c
algorithm
bit-manipulation
green_t
источник
источник
Ответы:
ПРИМЕЧАНИЕ . Все приведенные ниже алгоритмы написаны на языке C, но должны быть совместимы с выбранным вами языком (только не смотрите на меня, когда они не такие быстрые :)
Параметры
Недостаточно памяти (32-разрядная
int
, 32-разрядная машина) ( отсюда ):Со знаменитой страницы Bit Twiddling Hacks :
Самый быстрый (справочная таблица) :
Вы можете расширить эту идею до 64-битных
int
с или обменять память на скорость (при условии, что ваш кэш данных L1 достаточно большой) и инвертировать 16 битов за раз с помощью таблицы поиска с 64Кб.другие
просто
Быстрее (32-битный процессор)
Быстрее (64-битный процессор)
Если вы хотите сделать это на 32-битной системе
int
, просто поменяйте местами биты в каждом байте и измените порядок байтов. То есть:Полученные результаты
Я проверил два наиболее многообещающих решения: таблицу поиска и побитовое И (первое). Тестовый компьютер представляет собой ноутбук с 4 ГБ памяти DDR2-800 и Core 2 Duo T7500 с частотой 2,4 ГГц, 4 МБ кэш-памяти второго уровня; YMMV. Я использовал gcc 4.3.2 на 64-битном Linux. OpenMP (и привязки GCC) использовались для таймеров с высоким разрешением.
reverse.c
reverse_lookup.c
Я испробовал оба подхода с несколькими разными оптимизациями, провел 3 испытания на каждом уровне, и каждое испытание изменило 100 миллионов случайных
unsigned ints
. Для варианта таблицы поиска я попробовал обе схемы (варианты 1 и 2), приведенные на странице побитовых хаков. Результаты показаны ниже.Побитовое И
Таблица поиска (вариант 1)
Таблица поиска (вариант 2)
Вывод
Используйте таблицу поиска с опцией 1 (адресация байтов не удивительно медленная), если вы беспокоитесь о производительности. Если вам необходимо выжать из системы каждый последний байт памяти (и вы можете, если вам небезразлична производительность обращения битов), оптимизированные версии подхода побитового И не слишком потрепанные.
Предостережение
Да, я знаю, что эталонный код - полный взлом. Предложения о том, как его улучшить, приветствуются. Что я знаю о:
ld
взорвался из-за какой-то сумасшедшей ошибки переопределения символов), поэтому я не верю, что сгенерированный код настроен для моей микроархитектуры.32-битный
РЕДАКТИРОВАТЬ: я также пытался использовать
uint64_t
типы на моей машине, чтобы увидеть, есть ли какое-либо повышение производительности. Производительность была примерно на 10% выше, чем у 32-битных, и была почти одинаковой, независимо от того, использовали ли вы только 64-битные типы для инвертирования битов на двух 32-битныхint
типах за раз, или же вы действительно инвертировали биты вдвое меньше, чем 64-битные. битовые значения. Код ассемблера показан ниже (для первого случая биты обращения для двух 32-битныхint
типов одновременно):источник
Этот поток привлек мое внимание, так как он имеет дело с простой проблемой, которая требует большой работы (циклы ЦП) даже для современного ЦП. И однажды я тоже стоял там с той же проблемой #% "#". Я должен был перевернуть миллионы байтов. Однако я знаю, что все мои целевые системы основаны на современных технологиях Intel, поэтому давайте начнем оптимизацию до крайности !!!
Поэтому я использовал код поиска Мэтта Дж в качестве базы. система, на которой я бенчмаркинг - это i7 haswell 4700eq.
Бит Мэтта Дж, ищущий бит 400 000 000 байтов: около 0,272 секунды.
Затем я попытался выяснить, может ли компилятор Intel ISPC векторизовать арифметику в обратном порядке.
Я не собираюсь утомлять вас своими выводами, так как я много пытался помочь компилятору найти материал, так или иначе, в результате у меня была производительность около 0,15 секунды, чтобы перехватить 400 000 000 байтов. Это большое сокращение, но для моего приложения это все еще слишком медленно ..
Поэтому люди позволяют мне представить самый быстрый в мире процессор на базе Intel. Закрыто в:
Время до 600000000 байт: 0,050082 секунды !!!!!
Printf для отладки ..
Вот рабочая лошадка:
Код занимает 32 байта, а затем маскирует кусочки. Высокий клев смещается вправо на 4. Затем я использую vpshufb и ymm4 / ymm3 в качестве справочных таблиц. Я мог бы использовать одну справочную таблицу, но тогда мне пришлось бы сдвинуть влево, прежде чем ИЛИ снова откусить кусочки.
Есть даже более быстрые способы перевернуть биты. Но я связан с одним потоком и процессором, так что это было самое быстрое, чего я мог достичь. Можете ли вы сделать более быструю версию?
Пожалуйста, не комментируйте использование внутренних эквивалентных команд компилятора Intel C / C ++ ...
источник
pshub
, потому что в конце концов лучший попконт также сделан с этим! Я бы написал это здесь, если бы не ты. Престижность.popcnt
,tzcnt
иpext
все на порту 1. Таким образом, каждыйpext
илиtzcnt
стоит вамpopcnt
пропускной способности. Если ваши данные хранятся в кеше L1D, самый быстрый способ подсчета массива на процессорах Intel - это AVX2 pshufb. (У Ryzen есть 4 на тактовуюpopcnt
пропускную способность, так что это, вероятно, оптимально, но у семейства Bulldozer есть 1 на 4 тактовыхpopcnt r64,r64
... agner.org/optimize ).Это еще одно решение для людей, которые любят рекурсию.
Идея проста. Разделите ввод на половину и поменяйте местами две половины, продолжайте, пока не достигнете одного бита
Вот рекурсивная функция для ее решения. (Обратите внимание, что я использовал беззнаковые целые, поэтому он может работать для входных данных размером до sizeof (unsigned int) * 8 бит.
Это вывод:
источник
numBits
и int, когда вы делите 3 на 2 для параметра функции, оно будет округлено до 1?Ну, это, конечно, не будет ответом, как у Мэтта Джей, но, надеюсь, он все равно будет полезен.
Это в точности та же идея, что и в лучшем алгоритме Мэтта, за исключением того, что есть небольшая инструкция BSWAP, которая меняет байты (а не биты) 64-битного числа. Таким образом, b7, b6, b5, b4, b3, b2, b1, b0 становятся b0, b1, b2, b3, b4, b5, b6, b7. Поскольку мы работаем с 32-битным числом, нам нужно сместить наше число с заменой байтов на 32 бита. Это только оставляет нас с задачей замены 8 бит каждого байта, что сделано и вуаля! были сделаны.
Время: на моей машине алгоритм Мэтта выполнялся за ~ 0.52 секунды за испытание. Мой пробежал примерно за 0,42 секунды за испытание. На 20% быстрее не плохо, я думаю.
Если вас беспокоит доступность инструкции BSWAP, в Википедии перечислена инструкция BSWAP как добавляемая с 80846, которая вышла в 1989 году. Следует отметить, что Википедия также утверждает, что эта инструкция работает только с 32-битными регистрами, что явно не Случай на моей машине, он очень работает только на 64-битных регистрах.
Этот метод будет одинаково хорошо работать для любого интегрального типа данных, поэтому метод можно обобщить тривиально, передавая желаемое количество байтов:
который затем можно назвать так:
Компилятор должен иметь возможность оптимизировать дополнительный параметр (при условии, что компилятор указывает на функцию), и в этом
sizeof(size_t)
случае сдвиг вправо будет полностью удален. Обратите внимание, что GCC по крайней мере не может удалить BSWAP и сдвиг вправо, если он пройденsizeof(char)
.источник
unsigned long long int
которые должны быть не менее 64 бит, как здесь и здесьОтвет Андерса Седрониуса предоставляет отличное решение для людей, которые имеют процессор x86 с поддержкой AVX2. Для платформ x86 без поддержки AVX или платформ, отличных от x86, любая из следующих реализаций должна работать хорошо.
Первый код представляет собой вариант классического метода двоичного разделения, закодированный для максимального использования логики сдвига плюс логика, полезной на различных процессорах ARM. Кроме того, он использует генерацию маски «на лету», которая может быть полезна для процессоров RISC, которые в противном случае требуют нескольких инструкций для загрузки каждого 32-битного значения маски. Компиляторы для платформ x86 должны использовать постоянное распространение для вычисления всех масок во время компиляции, а не во время выполнения.
В томе 4А «Искусства компьютерного программирования» Д. Кнут показывает умные способы обращения битов, которые на удивление требуют меньше операций, чем классические двоичные алгоритмы разбиения. Один такой алгоритм для 32-битных операндов, который я не могу найти в TAOCP, показан в этом документе на веб-сайте Hacker's Delight.
Используя компилятор Intel C / C ++ 13.1.3.198, обе из вышеперечисленных функций автоматически векторизуют нужные
XMM
регистры. Они также могут быть векторизованы вручную без особых усилий.На моем IvyBridge Xeon E3 1270v2 с использованием автоматического векторизованного кода 100 миллионов
uint32_t
слов были инвертированы в битах за 0,070 секунды с использованиемbrev_classic()
и 0,068 секунды с использованиемbrev_knuth()
. Я позаботился о том, чтобы мой тест не ограничивался пропускной способностью системной памяти.источник
brev_knuth()
? Атрибуция в PDF от Восхищения Хакера, кажется, указывает, что эти числа непосредственно от самого Кнута. Я не могу утверждать, что достаточно хорошо понял описание Кнутом основополагающих принципов проектирования в TAOCP, чтобы объяснить, как были получены константы или как можно было бы вывести константы и коэффициенты сдвига для произвольных размеров слов.Предполагая, что у вас есть массив битов, как об этом: 1. Начиная с MSB, вставьте биты в стек один за другим. 2. Вставьте биты из этого стека в другой массив (или в тот же массив, если вы хотите сэкономить место), поместив первый выданный бит в MSB и перейдя к менее значимым битам оттуда.
источник
Собственная инструкция ARM "rbit" может сделать это с 1 циклом процессора и 1 дополнительным регистром процессора, который невозможно превзойти.
источник
Это не работа для человека! ... но идеально подходит для машины
Это 2015 год, через 6 лет после того, как этот вопрос был впервые задан. Компиляторы с тех пор стали нашими хозяевами, и наша задача как людей - помогать им. Итак, как лучше всего передать наши намерения машине?
Реверсирование битов настолько распространено, что вам нужно задаться вопросом, почему постоянно растущий ISA в x86 не содержит инструкции сделать это за один раз.
Причина: если вы дадите компилятору свое истинное краткое намерение, инверсия битов займет всего ~ 20 циклов ЦП . Позвольте мне показать вам, как создать reverse () и использовать его:
Компиляция этого примера программы с версией Clang> = 3.6, -O3, -march = native (протестировано с Haswell), дает код качества художественного произведения с использованием новых инструкций AVX2 с временем выполнения 11 секунд, обрабатывающим ~ 1 миллиард обратных () с. Это ~ 10 нс на реверс (), при этом цикл ЦП составляет 0,5 нс, при условии, что 2 ГГц дают нам целых 20 тактов процессора.
Предостережение: этот пример кода должен оставаться достойным эталоном в течение нескольких лет, но в конечном итоге он начнет показывать свой возраст, когда компиляторы станут достаточно умными, чтобы оптимизировать main (), чтобы просто напечатать окончательный результат вместо того, чтобы что-то вычислять. Но пока это работает в демонстрации реверса ().
источник
Bit-reversal is so common...
Я не знаю об этом. Я работаю с кодом, который работает с данными на битовом уровне практически каждый день, и я не могу вспомнить, чтобы когда-либо имел эту конкретную потребность. В каких сценариях это нужно? - Не то чтобы это не было интересной проблемой для самостоятельного решения.Конечно, очевидный источник взломанных битов здесь: http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious
источник
Я знаю, что это не C, а asm:
Это работает с битом переноса, так что вы можете сохранить флаги тоже
источник
rcl
перейти на CFvar1
вместо того,shl
чтобы не читать флаги. (Илиadc dx,dx
) Даже с этим исправлением это смехотворно медленно, используя медленныеloop
инструкции и сохраняяvar1
в памяти! На самом деле я думаю, что это должно производить выходные данные в AX, но это сохраняет / восстанавливает старое значение AX поверх результата.Реализация с низким объемом памяти и быстрее всего.
источник
Ну, это в основном то же самое, что и первый «reverse ()», но он 64-битный и требует только одну непосредственную маску для загрузки из потока команд. GCC создает код без переходов, поэтому это должно быть довольно быстро.
источник
Мне было любопытно, как быстро будет очевидное сырое вращение. На моей машине (i7 @ 2600) среднее значение для 1 500 150 000 итераций составляло
27.28 ns
(более случайного набора из 131 071 64-разрядных целых чисел).Преимущества: количество необходимой памяти мало, а код прост. Я бы сказал, что это не так уж и много. Требуемое время является предсказуемым и постоянным для любого ввода (128 арифметических операций SHIFT + 64 логических операции И + 64 операции логического ИЛИ).
Я сравнил с лучшим временем, полученным @Matt J - у которого есть принятый ответ. Если я правильно прочитал его ответ, лучшее, что он получил, - это
0.631739
секунды на1,000,000
итерации, что приводит к среднему значению631 ns
за оборот.Ниже приведен фрагмент кода:
источник
Возможно, вы захотите использовать стандартную библиотеку шаблонов. Это может быть медленнее, чем вышеупомянутый код. Однако, мне кажется, это понятнее и проще для понимания.
источник
общий
С кодом. Используя в качестве примера 1-байтовые входные данные num.
источник
Как насчет следующего:
Маленький и простой (правда, только 32-битный).
источник
Я думал, что это один из самых простых способов обратить вспять бит. пожалуйста, дайте мне знать, если есть какая-то ошибка в этой логике. в основном в этой логике мы проверяем значение бита в позиции. установите бит, если значение равно 1 в обратном положении.
источник
источник
k
всегда имеет степень 2, но компиляторы, вероятно, не докажут это и не превратят его в бит-сканирование / сдвиг.Я думаю, что самый простой метод, который я знаю, следует.
MSB
является входом иLSB
является «обратным» выходом:источник
источник
Еще одно решение на основе циклов, которое быстро завершается при низком числе (в C ++ для нескольких типов)
или в C для беззнакового целого
источник
Похоже, что многие другие сообщения беспокоятся о скорости (то есть лучший = самый быстрый). Как насчет простоты? Рассматривать:
и надеюсь, что умный компилятор оптимизирует для вас.
Если вы хотите изменить более длинный список битов (содержащих
sizeof(char) * n
биты), вы можете использовать эту функцию для получения:Это обратит [10000000, 10101010] в [01010101, 00000001].
источник
ith_bit = (c >> i) & 1
. Также сохраняйте SUB, сдвигаяreversed_char
вместо сдвига бит, если только вы не надеетесь, что он скомпилируется на x86 вsub something
/bts reg,reg
для установки n-го бита в регистре назначения.Обращение битов в псевдокоде
источник -> байт, подлежащий обращению b00101100 пункт назначения -> обратный, также должен иметь тип без знака, чтобы знаковый бит не распространялся вниз
копировать в temp так, чтобы оригинал не затрагивался, также должен быть беззнакового типа, чтобы бит знака не сдвигался автоматически
LOOP8: // сделать это 8 раз, если bytecopy <0 (отрицательно)
источник
Мое простое решение
источник
i
? Кроме того, что это за магическая константа* 4
? ЭтоCHAR_BIT / 2
?Это для 32 бит, нам нужно изменить размер, если мы рассмотрим 8 бит.
Чтение входного целого числа "num" в порядке LSB-> MSB и сохранение в num_reverse в порядке MSB-> LSB.
источник
источник