Как реализовать без цикла операцию над битовыми масками, которая для двух битовых масок a и b ширины n дает битовую маску c ширины 2 * n со следующими свойствами:
i-й бит вcустанавливается только при наличииj-го бита вaиk-го бита вbиj + k == i
Реализация С++:
#include <bitset>
#include <algorithm>
#include <iostream>
#include <cstdint>
#include <cassert>
#include <x86intrin.h>
std::uint64_t multishift(std::uint32_t a, std::uint32_t b)
{
std::uint64_t c = 0;
if (_popcnt32(b) < _popcnt32(a)) {
std::swap(a, b);
}
assert(a != 0);
do {
c |= std::uint64_t{b} << (_bit_scan_forward(a) + 1);
} while ((a &= (a - 1)) != 0); // clear least set bit
return c;
}
int main()
{
std::cout << std::bitset< 64 >(multishift(0b1001, 0b0101)) << std::endl; // ...0001011010
}
Можно ли его реализовать без цикла, используя некоторые битовые трюки или некоторые инструкции x86?
std::coutзанимает в этом коде на порядок больше времени, чем все остальные строки вместе взятые. - person Jesper Juhl schedule 01.03.2018uint32_tи возвращаетuint64_t, а не программу, которая выводит постоянный результат компиляции. Затем вы можете посмотреть на сгенерированный компилятором asm с включенной оптимизацией (по крайней мере, для случая, когда он не встроен в вызывающую программу с одним из операндов, являющимся константой). - person Peter Cordes schedule 05.03.2018