?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Next Entry
bithacks
nyaload
_winnie
Выяснилось, что битовые операции для быстрого нахождения логарифмов и тп часто считаются мистикой, люди их боятся, старшие программисты заменяют на "простые понятные циклы, вдруг рванёт из потустороннего мира".
Ничего мистического тут нет, надо просто думать о числе как о контейнере битов, и помнить школьные правила сложения/вычитания в столбик. Битовые &|~ >> << дают очевидные операции над контейнером. Сложение и вычитание – дают предсказуемые операции, когда нет переноса в старший разряд. Или когда из круглого числа с хвостом нулей вычитают 1, то получаем такой же хвост из 12 (в десятичной системе – из девяток). Например, xyz5000 - 1 == xyz4999.

Вкратце (и нестрого) про представление отрицательных чисел. В байте могут храниться значения от -128 до 127. В безнаковом байте после добавления 1 к 11111111 (255) получается 0. Поэтому если считать для байта со знаком что 255 означает -1, 254 это -2 ..., 129 это -127, 128 это -128, то арифметика с плюс-минус-умножить даёт одинаковые результаты для безнаковых чисел и для представлений знаковых чисел. Например, -1*-1 == 1, и параллельно 0xFF*0xFF == 0xfe01,
Если байт от -128 до -1, то его битовая запись от 10000000 (-128) до 11111111 (-1). Если от 0 до 127 - то от 0000000 до 01111111 (127). Весьма удобно, что знак определяется старшим битом.
Можно чуть строже: делим все целые числа на 256 подмножеств, по признаку остатка при делении на 256, эти подмножества будут нашими новыми числами, определяем сложение/умножение подмножеств a, b как подмножество c содержащее сумму/произведение любых элементов a и b, доказываем корректность (неважно какие элементы a, b выбрать). Получаем что для результата по модулю неважно что вместо -1 взяли 255, подробней http://ru.wikipedia.org/wiki/Сравнение_по_модулю .
(Без)знаковость в арифметических операциях на биты не влияет, если нам удобно думать что числа от -1 до 254 или от -100 до 155, то пожалуйста, только сравнение будет своё, а +-* можно оставить.

Неочевидных арифметических трюков мало, самые часто использующиеся - это равенство (~x + 1) == (0 - x) и определение знака числа через x >> 31 (>>63 для 64-битных, >>7 для signed byte и тп).
  1. Первое равенство (~x + 1) == (0 - x) получается вычитанием в столбик. Вычтем из байта 11111111 число xxxxxxxx, 1-x даёт инверсию бита x. Вычитание из 11111111 это вычитание из представления -1. Таким образом -1-x == ~x.

  2. Второе равенство следует из определения побитового сдвига для знаковых чисел. Когда биты сдвигаются вправо, надо чем-то заполнять место слева. Для безнаковых чисел туда кладуться просто нули, а для знаковых – старший бит, что бы сохранился знак числа. Таким образом, число (Yxxxxxxx >> 7) превратится в YYYYYYYY, то есть в 0 или в -1. Также, если у нас есть выражение mask, которое равно -1 или 0, то mask xor x равно либо x, либо ~x.

  3. Так же постоянно используется прием (трюком это сложно назвать, слишком просто) замены (a ? x : y) на (a_mask & x) | (~a_mask & y), где a_mask это 00000000 или 11111111.

Давайте разберём несколько примеров.
1) Абсолютное значение числа.
mask = x >> 31; result = (x + mask ) xor mask.
Суть алгоритма: когда x > 0, то mask это 0, и (x+0 xor 0) даёт x. Когда x < 0, то mask это -1 (см. трюк 2). (x-1) xor (-1) это побитно инвертированный x. Инвертация (x-1) это эквивалетно -1-(x-1) (см. трюк 1), то есть -x.
Note: многие C/C++ компиляторы вызов библиотечного макроса abs могут оптимизировать лучше, как встроенную операцию. Это пример, как можно писать свои бит-хаки, когда нет хорошей библиотечной реализации и последняя версия g++/icc плохо читает ваши мысли. Напр. мысль (x < y) ? x : y они угадывают.
2) является ли число степенью двойки. Очень красивое решение:
If (x&(x-1)) { не степень двойки } else { x – степень двойки }.
Если x - степень двойки, то оно выглядит как 10…000. Тогда x-1 это 1…111.
000100…00 &
000011…11 = 000000…00

Если x НЕ степень двойки, то после старшего бита будут какие-то единицы, которые защитят старший бит от обнуления после вычитания. В x-1 старший бит останется на месте, и в x&(x-1) этот бит останется, давая ненулевой результат.
3) округление до следующей степени двойки.
Запишем число в бинарной системе счисления. Что бы округлить до большей степени двойки, важно положение только старшего бита. Если число выглядит как X = 0001xxxxx, то после X = X | (X >> 1) уже выглядит как 00011xxxx. Эту пару битов 11 можно ещё раз удвоить, X = X | (X >> 2), получим 0001111xx и после достаточного количества применений число будет выглядеть как 00….00111….11. После добавления 1 к числу с одними 1 на хвосте получится такой же хвост нулей и 1 перед ним. Это и будет округлением числа до большей следующей степени двойки. Что бы округлить до большей-или-равной, достаточно вычесть 1 из числа X перед применением алгорима.

int bit_mask_after_hi(unsigned int x)
{
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x;
}

unsigned next_pow_of_2 = bit_mask_after_hi(x-1) + 1;
_Winnie C++ Colorizer

4) Подсчёт числа битов. Таблица может оказаться быстрей, но есть способ без. И количество арифметических операций растёт как логарифм битности, а не линейно.
Дело в том, что можно в одном числе хранить сразу два числа. И можно их сложить одновременно, если одно не налезает на другое. Например,
055000017 +
061000090 =
116000107

Разобьём число на два: обнулим каждую четную цифру и каждую нечетную. Напр. abcd на a0c0 и 0b0d. Сложим a0c c b0d. Затем разделим на блоки по две цифры, и опять разделим на два числа, по четным блоками и нечтным, сложим два числа. Затем на блоки по четыре цифры, и тд. В конце концов когда блок стаент размером с исходное число – получим сумму цифр. Для двоичной арифметики для обнуления блоков используются маски 101010101, 11001100, 11110000 и тд.
int bit_count(unsigned int x)
{
x = ((x & 0xAAAAAAAAU) >> 1) + (x & 0x55555555U);
x = ((x & 0xCCCCCCCCU) >> 2) + (x & 0x33333333U);
x = ((x & 0xF0F0F0F0U) >> 4) + (x & 0x0F0F0F0FU);
x = ((x & 0xFF00FF00U) >> 8) + (x & 0x00FF00FFU);
return (x >> 16) + (x & 0xFFFF);
}
_Winnie C++ Colorizer

5) логарифм числа (т.е. позиция старшего бита, номер мип-мапа, глубина двоичного дерева, количество шагов в делении пополам и тд).
Тут всё просто, совмещаем алгоритм 3) и 4). Сначала все биты числа младше старшего делаем единичными, а затем считаем число битов.
int bit_hi_index(unsigned int x)
{
return bit_count(bit_mask_after_hi(x));
}
_Winnie C++ Colorizer


Уф, я устал, больше хаков смотрите здесь:
http://graphics.stanford.edu/~seander/bithacks.html
Если будете копировать код, подумайте, считать ли 0 степенью двойки или есть ли у 0 осмысленный логарифм.


  • 1
Ага. Эта функция была утащена во все игровые движки, пока SSE не захватила мир :)
Ещё http://aruslan.livejournal.com/99322.html , и
int f2i(float x)
{
  const int magic = (150<<23)|(1<<22);
  x += *(float*)&magic;
  return *(int*)&x - magic;
}



(Deleted comment)
А вообще, конечно, нужно читать “Hacker's Delight”, где как раз описаны всякие битовые трюки очень подробно. А пошло это всё, насколько я понимаю, из HAKMEM.

спасибо, познавательно :)
вопросы 3 и 4 я не так давно получал на собеседованиях )

если не секрет, куда такое спрашивали?

хорошо, что ты сейчас об этом написал - спустя 2-3 года на сервере с явой многое из этого и тебе будет казаться "мистикой из потустороннего мира" ;)

это какая то мистика из потустороннего мира
те кто так делает - явно заключили пакт с бесами
на костер их!

> люди их боятся, старшие программисты заменяют на "простые понятные циклы, вдруг рванёт из потустороннего мира".
...
> Если будете копировать код, обязательно тестируйте, легко нарваться на ошибку плюс-минус-один или на то что таблицы быстрей чем бит-хаки, или что при касте int*<->float* нарветесь на -fno-strict-aliasing

Помойму первое со вторым находится в предивной гармонии.

Ошибки +-один касаются и "простых циклов". Можешь сходу сказать индекс сташего бита в int32, если цикл показал что перед ним k нулей?
Таблицы тем более.

>>63 это жесть. Рассчет на то что компилер не вызовет сдвиг а прочтет мысли как с ror/rol?

Не знаю asm для 64-битных режимов процессоров, есть ли у него операции с 64-битными числами как с одним целым?

самые интересные эффекты от применения минуса в битовых операциях. например (-x & x) оставляет только младший ненулевой бит числа.

Большое спасибо за интересную подборку. Но лично на меня самое большой впечатление произвел тот факт, что битовые операции хорошо использовать для симуляции недетерминированных автоматов. Типа, параллелизм внутри компьютерного слова.

Вообще говоря, я не понимаю, зачем такое постить. Есть настоящая библия по битхакам, называется Hacker's Delight. Есть еще ряд источников вроде http://graphics.stanford.edu/~seander/bithacks.html , и даже в Wayback Machine можно найти битхаки с HAKMEM'а (для удобства стоит даже выкачать, потому что там тысячи страниц по битхакам, от GF2-Гаусса до быстрых кватернионов).
В конце-концов, есть superoptimizer'ы (с их разновидностью peephole), которые все эти трюки способны изобрести, только скормите им описание команд процессора.

GF2 Гаусс? Что это?
PS: многие трюки компьютеры не могут изобрести.

  • 1