- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
inline int8_t log2(size_t value)
{
static constexpr int8_t table[64] =
{
63, 0, 58, 1, 59, 47, 53, 2,
60, 39, 48, 27, 54, 33, 42, 3,
61, 51, 37, 40, 49, 18, 28, 20,
55, 30, 34, 11, 43, 14, 22, 4,
62, 57, 46, 52, 38, 26, 32, 41,
50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16, 9, 12,
44, 24, 15, 8, 23, 7, 6, 5
};
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
value |= value >> 32;
return table[((value - (value >> 1)) * 0x07EDD5E59A4E28C2) >> 58];
}
Случайно наткнулся на такую магию.
Вроде проще способ был - без массивов и плясок с умножением на магическую константу с переполнением.
https://en.wikipedia.org/wiki/Find_first_set#Tool_and_library_support
https://www.go4expert.com/articles/builtin-gcc-functions-builtinclz-t29238/
https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
Built-in Function: int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
Built-in Function: int __builtin_clzl (unsigned long)
Similar to __builtin_clz, except the argument type is unsigned long.
Built-in Function: int __builtin_clzll (unsigned long long)
Similar to __builtin_clz, except the argument type is unsigned long long.
Сдвиги забивают все младшие биты единицами.
0b00010101 превращается в
0b00011111.
Разность оставляет установленным только один бит:
0b00011111
-
0b00001111
=
0b00010000
Итого: сдвиги и разность оставляют единичным только самый старший единичный бит, остальные обнуляют.
Умножение на магическую константу числа, у которого установлен только один бит, эквивалентен сдвигу магической константы.
0b00010000 * 0x07EDD5E59A4E28C2 == 0x07EDD5E59A4E28C2 << 4.
Для произвольного value получим 0x07EDD5E59A4E28C2 << log_2(value).
Двигая 64-битное число вправо на 58, мы оставляем только 6 старших битов.
Т. е. все эти манипуляции вырезают из 0x07EDD5E59A4E28C2 шесть смежных битов. Положение вырезанного куска зависит от log_2(value). А дальше происходит выборка из таблицы.
Почему нельзя было объявить магическую константу вроде 0xFEDBCA986543210 (тогда бы и таблица не понадобилась) и использовать сдвиги, кратные четырём? Потому что 64-битной константы не хватит для хранения 64 значений (мы в неё сможем затолкать только 16). Значит, нужно либо использовать 64*6=384-битную константу, либо... придумать алгоритм зожатия, что здесь и было продемонстрировано.
inline int8_t log2(size_t value)
Да ну?
Вот так легче читается.
Ну ладно, исправил:
http://govnokod.ru/22508
милый Борманд жду тибя
Разумеется, в системе команд процессоров интеловского семейства (да и других тоже) уже давно появились встроенные команды для решения этой задачи, на к которым в компиляторах привязаны соответствующие нестандартные средства: `_BitScanReverse64` в MSVC и `__builtin_clzll` в GCC. Но, разумеется, использование этих нестандартных свойств без предоставления fallback implementation не допускается: это будет классикой жырного говнокодинга. Вышеприведенный вариант как раз является хорошим вариантом fallback implementation.
Так что эту заявку на говнокод я вынужден отклонить. Учите матчасть.
Вот ты меня унизил сейчас.
надо было сделать вид что ты знаешь что такое последовательность де Брёйна.
Дескать: "ах, да я каждый день с ней сталкиваюсь когда пишу валидаторы формочек на JS"
Нет, не соглашусь. Я считаю что наилучшим вариантом будет втулить туда все возможные нестантартные интринсики через #ifdef директивы препроцессора, а если ничего из этого по каким-либо причинам не подходит, надо чтобы это просто не собиралось. И тогда уже пусть программист пилит там себе реализацию. Поясню:
Если никакие интнинсики не подошли, скорее всего кто-то это собирает под какую-то нестандартную платформу каким-то нестандартным компилятором, например это вполне может оказаться какой-нибудь AVR микроконтроллер. Если это окажется AVR микроконтроллер без поддержки инструкций умножения, то вышеозначенная fallback implementation, использующая умножение, скорее всего развернется в очень жирный и неэффективный машинный код, что может быть критично для микроконтроллера, и лучше бы под этот случай написать другую fallback implementation, например через какие-нибудь сдвиги, или же вообще на ассемблерных вставках
astandj <a href= http://buyviagra24ph.com >generic viagra</a>
case dismissed
Ого, давненько вас не было видно. Заходите почаще, а то доля интересного чтива на сайте стремится к нулю на фоне разбушевавшихся ботов.
http://cdn.intechopen.com/pdfs-wm/5296.pdf
Знаете?
погугли "0x5f3759df"
А история-то в чём?
что "волшебная" константа позволяет примерно посчитать обратный корень быстрее чем на fpu
я в математике слаб
> сомнительный битодроч
> value |= value >> 32;
Ай! Нога!