Как умножить бит 1 числа А и бит 2 числа В или операции с битовыми матрицами

А теперь более полная постановка задачи. Нужно комбинировать по определенной «битовой» формуле большое количество байт. Формула может меняться. Например: C=a1*b2+a3*b4+a1*b4+a4*b1 , где a1a2a3a4 - первое 4-битовое число, b1b2b3b4 - второе 4-битовое число, * - битовое И, + - битовое ИЛИ. Еще операцию можно записать в виде 4x4 матрицы:

Все это нужно делать быстро.

Какие есть для этого инструменты? Подозреваю что это где-то в районе mmx, sse и других подобных инструкций, есть такое?

думаю, начать стоит с

Отдельные «И» можно заменить на побитовое «И» между двумя регистрами. «ИЛИ» можно заменить на сранение регистра с нулём, т.к. если есть хоть один ненулевой бит, «ИЛИ» даст 1. Больше всего времени займёт расположение битов в нужном порядке.

Они же все работают со столбцами действительных чисел. А ТСу нужны биты (полагаю, что операнды у него в «упакованном» виде, т. е. затраты на преобразование будут сравнимы с затратами на вычисление).

Сколько разных «формул» ожидается? Известны ли все используемые «формулы» на момент запуска алгоритма? Если нет, то как часто они будут меняться (сколько пар операндов будет обработано по одной формуле до её смены)?

К чему я клоню: к табличке из всех возможных результатов операции. Для двух полубайт табличка займёт всего 256 байт, а для двух байт — 64K. Последнее, конечно, в L1 не влезает, но в L2 точно. Бегло посмотрел на MMX/SSE — там ничего подобного нет, потому что оно создавалось для другого (для работы со столбцами из floating-point чисел, а у тебя биты; см. пред. ответ). prischeyadro прав, сложнее всего с выборкой/перемешиванием отдельных битов.

Имеем 4 (аргумент a) + 4 (аргумент b) + 16 (результат) = 24 бит. Столько бит достаточно, что бы закодировать любую твою операцию. Теперь разработай метод получения операции по конкретному числу и будет тебе щастье.

Ах да, я дегенерат: поскольку у тебя результат операции — это один бит, табличку тоже можно упаковать, и тогда в L1 она спокойно влезет даже для операндов байтового размера.

Формулы заранее неизвестны. Они определяются входными данными (типа обучение).Вообще хочется сделать реализацию логических схем по типу такого: https://ru.wikipedia.org/wiki/Карта_Карно (не лучшее описание, если надо расскажу короче). Я только упростил задачу полагая что в перемножении (логическое И) лишь два аргумента. Ну, и формулы не упрощаются, иначе алгоритм совсем усложнится.

Ну, и еще фишка в том, что данных обрабатывать нужно много, потому нужна скорость.

Для двух полубайт табличка займёт всего 256 байт, а для двух байт — 64K.

Это первое что мне пришло в голову. Потенциально длинна входного блока больше, так что не подходит.

prischeyadro прав, сложнее всего с выборкой/перемешиванием отдельных битов.

Впринципе, алгоритм реалиуется парой логических операций. Не пробовал, но по идее так:

Но если размер входного блока вырастает, то таких операций получается много. А по условиям задачи нужно делать быстро. Вот и подумал на всякие чудо-инструкции современных процессоров.

Еще по идее можно разложить на операции с матрицами (эх, матан, пока не смог вспомнить, но уверен что есть).

Бегло посмотрел на MMX/SSE — там ничего подобного нет

Странно, мне казалось, что это типовая задача. А операций с битовыми матрицами тоже нет?

Бегло посмотрел на MMX/SSE — там ничего подобного нет

Странно, мне казалось, что это типовая задача. А операций с битовыми матрицами тоже нет?

Есть там битовая арифметика, это intelfx слишком уж бегло смотрел. https://software.intel.com/sites/landingpage/IntrinsicsGuide/ - выбирай слева «Bit manipulation», «Logical», «Shift» и т.п., будет видно что можно сделать

В разделе 7.1.3 у Кнута описываются битовые трюки, может будет полезно глянуть. Прямо решения задачи там не будет, но есть всякие перемешивания бит и различное комбинирование, какие-то идеи может пригодятся. Там же говорится, что в реальных процессорах в отличии от MMIX, таких инструкций, к сожалению, нет. При этом для 32- и 64-битных чисел там есть быстрые варианты ряда операций, для больших размеров сложнее.

Забавный сайт, спасибо.

Просмотрел бегло. Вариантов с битовыми матрицами не нашел, но много инструкций AVX-512, которые могут помочь алгоритму выше. Правда, я так понял, что это не шибко популярный набор инструкций. Эх. :(

Вопрос не в алгоритме. Придумать алгоритм не сложно. Вопрос в скорости - процессорных инструкциях.

Так там описаны способы замены кучи циклов и сдвигов на операции с целыми большей разрядности как раз с целью выжать максимум используя пару-тройку инструкций. Речь ведь не о том, чтобы реализовать метод «в лоб» самым быстрым способом, а скорее найти метод, который при реализации на существующем оборудовании будет быстрым, а самый очевидный способ может просто не поддаваться оптимизации.

Почитай что такое ДНФ (дизьюктивная нормальная форма) для булевой функции 2х аргументов, вот тебе нужно её построить для случая когда функция задана таблицей. Математика умеет искаропки.

📎📎📎📎📎📎📎📎📎📎