Пушыстый (_winnie) wrote,
Пушыстый
_winnie

Categories:

bithacks

Выяснилось, что битовые операции для быстрого нахождения логарифмов и тп часто считаются мистикой, люди их боятся, старшие программисты заменяют на "простые понятные циклы, вдруг рванёт из потустороннего мира".
Ничего мистического тут нет, надо просто думать о числе как о контейнере битов, и помнить школьные правила сложения/вычитания в столбик. Битовые &|~ >> << дают очевидные операции над контейнером. Сложение и вычитание – дают предсказуемые операции, когда нет переноса в старший разряд. Или когда из круглого числа с хвостом нулей вычитают 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 осмысленный логарифм.
Tags: math, release, soft-dev, tips
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 40 comments