|
Трюки - манипуляции c битами
Трюки - манипуляции c битами
Автор: Аркадий Белоусов, письмо от 19 сентября 1999 года в эхоконференции fido7.RU.ALGORITHMS.
Примеры даны для языка Си. Если Вам требуется перевести трюки на другой язык, то запомните,
что в языке Си:
^ - Исключающее ИЛИ, & - И, | - ИЛИ, ~ - НЕ.
Подсчёт количества ненулевых бит в числе v за log2(v) проходов
На примере 8-битного числа:
v = (v & 0x55) + ((v >> 1) & 0x55);
v = (v & 0x33) + ((v >> 2) & 0x33);
return (v & 0x0f) + ((v >> 4) & 0x0f);
Число разбивается на группы бит одной длины (сперва по одному биту).
Затем значения соседних пар одновременно складываются и сохраняются в
новых группах в два раза большей длины до тех пор, пока не будут сложены
половинки числа.
Поскольку длина суммы двух чисел равна длине большего числа с битом для
переноса, поэтому для каждой группы в маске групп достаточно иметь единиц
не больше номера шага (то есть 1+log2 от длины группы). Hапример, для
подсчёта единичных бит в 32-битном числе (с оптимизацией):
#define g21 0x55555555ul
#define g22 0x33333333ul
#define g23 0x0f0f0f0ful
v = (v & g21) + ((v >> 1) & g21);
v = (v & g22) + ((v >> 2) & g22);
v = (v + (v >> 4)) & g23;
return (v + (v >> 8) + (v >> 16) + (v >> 24)) & 0x3f;
Для сокращения количества шагов можно суммировать тройки и т.д.:
#define g31 0x49249249ul
#define g32 0x381c0e07ul
v = (v & g31) + ((v >> 1) & g31) + ((v >> 2) & g31);
v = ((v + (v >> 3)) & g32) + ((v >> 6) & g32);
return (v + (v >> 9) + (v >> 18) + (v >> 27)) & 0x3f;
Сбросить младший ненулевой бит/проверить, является ли число степенью двойки:
(n - 1) & n
if((n - 1) & n == 0)
Выделить младший единичный бит:
((n - 1) ^ n) & n
((n - 1) & n) ^ n
~(n - 1) & n
Поменять местами значение двух переменных, не используя третью:
a ^= b ^= a ^= b;
Заменить одно значение на другое в переменной, которая может принимать только эти два значения:
v = (val1 + val2) - v;
v ^= val1 ^ val2;
Подсчитать номер младшего единичного бита (n должен быть ненулевым):
Привет для 32-битного числа.
k = 0;
if((n & 0xFFFF) == 0) k = 16, n >>= 16;
if((n & 0x00FF) == 0) k += 8, n >>= 8;
if((n & 0x000F) == 0) k += 4, n >>= 4;
if((n & 0x0003) == 0) k += 2, n >>= 2;
if((n & 0x0001) == 0) k += 1;
Подсчитать номер старшего единичного бита (если n=0, то k=32):
Привет для 32-битного числа.
k = 0;
if(n & 0xFFFF0000) k = 16, n >>= 16;
if(n & 0x0000FF00) k += 8, n >>= 8;
if(n & 0x000000F0) k += 4, n >>= 4;
if(n & 0x0000000С) k += 2, n >>= 2;
if(n & 0x00000002) k += 1;
Автор: Аркадий Белоусов (Arkady V.Belousov), ark@belous.munic.msk.su.
Перевод в HTML - Акжан Абдулин, akzhan@info.khv.ru, 6 октября 1999 года.
|
