О каких полезных трюках с побитовым кодом оператора должен знать разработчик?

использование побитовых операций над строками (символами)

преобразовать письмо строчные буквы:

• OR пробел => (x | ' ')
• результат всегда строчный, даже если буква уже строчная
• например. ('a' | ' ') => 'a';('A' | ' ') => 'a'

преобразовать письмо верхний:

• AND подчеркнуть => (x & '_')
• результат всегда прописной, даже если буква уже прописная
• например. ('a' & '_') => 'A';('A' & '_') => 'A'

инверсия письмо:

• XOR пробел => (x ^ ' ')
• например. ('a' ^ ' ') => 'A';('A' ^ ' ') => 'a'

письмо позиция в алфавите:

• AND by chr(31)/binary('11111')/(hex('1F') => (x & "\x1F")
• результат в 1..26 диапазон, регистр букв не важен
• например. ('a' & "\x1F") => 1;('B' & "\x1F") => 2

получаете письмо позиция в алфавит (для верхний

---

• побитовые операции над целыми числами(тип int)

---

получить максимальное целое число

int maxInt = ~(1 << 31);
int maxInt = (1 << 31) - 1;
int maxInt = (1 << -1) - 1;

получить минимальное целое

int minInt = 1 << 31;
int minInt = 1 << -1;

получить максимальную длину

long maxLong = ((long)1 << 127) - 1;

умножить на 2

n << 1; // n*2

делится на 2

n >> 1; // n/2

умноженное на m-ю степень 2

n << m;

делится на m-й степени 2

n >> m;

проверить нечетное число

(n & 1) == 1;

обмен двух значений

a ^= b;
b ^= a;
a ^= b;

получить абсолютное значение

(n ^ (n >> 31)) - (n >> 31);

получить максимум из двух значений

b & ((a-b) >> 31) | a & (~(a-b) >> 31);

получить мин двух значений

a & ((a-b) >> 31) | b & (~(a-b) >> 31);

проверить, есть ли у обоих тот же знак

(x ^ y) >= 0;

вычислить 2^n

2 << (n-1);

является ли факториал 2

n > 0 ? (n & (n - 1)) == 0 : false;

по модулю 2^n против m

m & (n - 1);

средние

(x + y) >> 1;
((x ^ y) >> 1) + (x & y);

получить m-й бит n (от низкого до высокого)

(n >> (m-1)) & 1;

установите M-й бит n в 0 (от низкого до высокий)

n & ~(1 << (m-1));

n + 1

-~n

n-1

~-n

получить номер контраста

~n + 1;
(n ^ -1) + 1; 

если (Х==а) х=б; Если (х==б) х=а;

x = a ^ b ^ x;

есть только три, которые я когда-либо использовать с любой частотой:

1. Набор бит: a / = 1

2. очистить немного: a & = ~(1

3. проверьте, что бит установлен: a & (1

вопросы вычислительные: идеи, алгоритмы, исходный код, Йорг Арндт (PDF). Эта книга содержит тонны материала, я нашел его по ссылке в http://www.hackersdelight.org/

среднее без переполнения

процедура для вычисления среднего (x + y)/2 из двух аргументы x и y-это

static inline ulong average(ulong x, ulong y)
// Return floor( (x+y)/2 )
// Use: x+y == ((x&y)<<1) + (x^y)
// that is: sum == carries + sum_without_carries
{
    return (x & y) + ((x ^ y) >> 1);
}

вы можете сжимать данные, например, совокупность целых чисел:

• смотрите, какие целочисленные значения появляются чаще в коллекции
• Используйте короткие битовые последовательности для представления значений, которые появляются более часто (и более длинные битовые последовательности для представления значений, которые появляются реже)
• объединить битовые последовательности: так, например, первые 3 бита в результирующем потоке битов могут представлять одно целое число, а затем следующее 9 бит другое целое число, и т. д.

Я использовал побитовые операторы для эффективной реализации вычислений расстояния для bitstrings. В моем приложении битовые строки использовались для представления позиций в дискретизированном пространстве (an octree, Если вам интересно, закодировано с Мортон заказ). Вычисления расстояния были необходимы, чтобы знать, попадают ли точки на сетке в пределах определенного радиуса.

подсчет установленных битов, поиск самого низкого / самого высокого установленного бита, поиск nth-сверху/снизу установленного бита и другие могут быть полезны, и стоит посмотреть на бит сложа хаки сайт.

тем не менее, такие вещи не важны изо дня в день. Полезно иметь библиотеку, но даже тогда наиболее распространенные способы использования являются косвенными (например, использование контейнера bitset). Кроме того, в идеале это будут стандартные библиотечные функции - многие из них лучше обрабатываются с помощью специализированного процессора инструкции на некоторых платформах.

1) деление / умножение на степень 2

foo >>= x; (делим на 2 степени)

foo <<= x; (умножить на степень 2)

2) поменять

x ^= y;
y = x ^ y;
x ^= y;

в то время как умножение/деление путем сдвига кажется отличным, единственное, что мне нужно было время от времени сжимать булевы в биты. Для этого вам нужно побитовое и/или, и, вероятно, битовое смещение/инверсия.

Я хотел, чтобы функция округляла числа до следующей наивысшей степени из двух, поэтому я посетил сайт Bit Twiddling, который был поднят несколько раз, и придумал это:

i--;
i |= i >> 1;
i |= i >> 2;
i |= i >> 4;
i |= i >> 8;
i |= i >> 16;
i++;

Я использую его на size_t тип. Вероятно, он не будет хорошо играть на подписанных типах. Если вы беспокоитесь о переносимости на платформы с разными типами размеров, посыпьте свой код #if SIZE_MAX >= (number) директивы в соответствующие места.