Самая быстрая функция для установки битов в один между двумя битами в целом числе без знака
У меня есть алгоритм для моделирования на суперкомпьютерах, который потребует много битовых манипуляций. Некоторым операциям понадобятся маски и, в частности, такая функция:
template <typename Type,
class = typename std::enable_if<std::is_integral<Type>::value>::type,
class = typename std::enable_if<std::is_unsigned<Type>::value>::type>
inline Type mask(const std::size_t first, const std::size_t last)
{
// Something
}
это сгенерирует маску типа Type где биты в диапазоне [first, last[ установлены в 1 (first а также last переменные времени выполнения)
Например:
mask<unsigned char>(3, 6) -> 00111000
Мне понадобятся сотни миллиардов этих масок, поэтому мне нужно, чтобы эта функция была максимально оптимизирована (но в простом стандарте C ++ 11). Как это сделать ?
Решение
return (1 << last) - (1 << first);
Другие решения
Вы можете составить справочную таблицу, и стоимость будет считана за одно чтение памяти. Если вы используете 32-битные элементы, таблица должна иметь размер 32×32 = 1024 слова в памяти (4 килобайта), поэтому она останется в кеше, если вы интенсивно ее используете. Даже для 64-битных элементов поиск в формате 64×64 составляет всего 4096 слов (32 килобайта).
Это выписка из стандарта:
Операторы смены
[Expr.shift]… Поведение не определено, если правый операнд отрицательный, или больше или равен длине в битах повышенного левого операнда.
Вот почему выражение «(1 << последний) — (1 << first) ‘не работает, когда last == sizeof (Type) * CHAR_BIT. Я предлагаю вам другую альтернативу, которая вычисляет значения во время компиляции, когда это возможно. Смотрите следующий пример:
#include <limits>
#include <iostream>
#include <bitset>template <class Integer>
constexpr Integer ones()
{
return ~static_cast<Integer>(0);
}template <class Integer>
constexpr Integer mask(std::size_t first, std::size_t last)
{
return (ones<Integer>() << first) &
(ones<Integer>() >> (std::numeric_limits<Integer>::digits - last));
}//Requires: first is in [0,8) and last is in (0,8]
void print8(std::size_t first, std::size_t last)
{
std::cout << std::bitset<8>(mask<unsigned char>(first, last)) << '\n';
}
int main()
{
print8(0,1); //000000001
print8(2,6); //001111100
print8(0,8); //111111111
print8(2,2); //000000000
static_assert(mask<unsigned char>(0,8) == 255,
"It should work at compile-time when possible");
}
может быть, просто небольшое изменение, чтобы отразить значение (в моем понимании) first а также last из примера, приведенного ОП.
#include <iostream>
#include <bitset>
using namespace std;
unsigned char mask( int first, int last) {
return (1 << (8-first)+1) - (1 << (8-last));
}
/*
*
*/
int main(int argc, char** argv) {
cout << bitset<8>(mask(3,6)) << endl; //prints:00111100
cout << bitset<8>(mask(2,6)) << endl; //prints:01111100
cout << bitset<8>(mask(1,3)) << endl; //prints:11100000
cout << bitset<8>(mask(1,7)) << endl; //prints:11111110
return 0;
}
detector