Show Menu
Cheatography

Трюки с битами Cheat Sheet by

На битовых операциях можно сделать очень много всего интересного, и работать оно будет очень быстро и занимать мало места. Огромный список битовых трюков и хаков можно посмотреть в этой статье [https://graphics.stanford.edu/~seander/bithacks.html] , их там очень много и все с примерами.

Целые

Установка nго бита
x | (1<­<n)
Выключение nго бита
x & ~(1<<n)
нверсия nго бита
x ^ (1<­<n)
Округление вниз
n >> 0
5.7812 >> 0
// вернёт 5
Умножение на 2
1n << 1;
Деление на 2
n >> 1;
Умножение на mую степень двойки
n << m;
Деление на mую степень двойки
n >> m;
Проверка на чётность (кратность 2)
(n & 1) == 1;
Максимум из двух
b & ((a-b) >> 31) | a & (~(a-b) >> 31);
Минимум из двух
a & ((a-b) >> 31) | b & (~(a-b) >> 31);
Проверка на одинаковый знак
(x ^ y) >= 0;
Смена знака
i = ~i + 1; // or
i = (i ^ -1) + 1; // i = -i
Вернёт 2n
1 << n;
Является ли число степенью 2
n > 0 && !(n & (n - 1));
Остаток от деления на 2n на m
m & ((1 << n) - 1);
Среднее
арифметическое
(x + y) >> 1;
((x ^ y) >> 1) + (x & y);
Получить mый бит из n (от младшего к старшему)
(n >> (m-1)) & 1;
Получить mый бит из n (от старшего к младшему)
n & ~(1 << (m-1));
Проверить включен ли nый бит
`if (x & (1<­<n)) {
  n-th bit is set
} else {
  n-th bit is not set
}
Выделение самого правого включе­нного бита
x & (-x)
Выделение самого правого выключ­енного бита
~x & (x+1)
Выделение правого включе­нного бита
x | (x+1)
Выделение правого выключ­енного бита
x & (x-1)
n + 1
-~n
n – 1
~-n
Получение отрица­тел­ьного значения
~n + 1;
(n ^ -1) + 1;
if (x == a) x = b;
if (x == b) x = a;
x = a ^ b ^ x;
Поменять смежные биты
((n & 10101010) >> 1) | ((n & 01010101) << 1)
Different rightmost bit of numbers m & n
(n^m)&-(n^m) // returns 2x where x is the position of the different bit (0 based)
Common rightmost bit of numbers m & n
~(n^m)­&(­n^m)+1 // returns 2x where x is the position of the common bit (0 based)
 

Целые

Округление до ближайшей степени двойки
unsigned int v; // работает только с 32 битными числами
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
Получение максим­ального целого
int maxInt = ~(1 << 31);
int maxInt = (1 << 31) - 1;
int maxInt = (1 << -1) - 1;
int maxInt = -1u >> 1;
Получение минима­льного целого
int minInt = 1 << 31;
int minInt = 1 << -1;
Получение максим­ального long
long maxLong = ((long)1 << 127) - 1;
Остаток от деления
n & 0b1; // на 2
n & 0b11; // на 4
n & 0b111; // на 8
И так далее
Проверка равенства
(a^b) == 0; // a == b
!(a^b) // исполь­зовать внутри if()
Обмен значениями
//version 1
a ^= b;
b ^= a;
a ^= b;
//version 2
a = a ^ b ^ (b = a)
Получение абсолю­тного значения
//version 1
x < 0 ? -x : x;
//version 2
(x ^ (x >> 31)) - (x >> 31);

Строки

Конвер­тир­овать в нижний регистр`
(x | ' ')
Пример: ('a' | ' ') => 'a' ; ('A' | ' ') => 'a'
Конвер­тир­овать в верхний регистр
(x & '_')
Пример: ('a' & '_') => 'A' ; ('A' & '_') => 'A'
Инверт­ировать регистр
(x ^ ' ')
Пример: ('a' ^ ' ') => 'A' ; ('A' ^ ' ') => 'a'
Позиция буквы в алфавите (англ)
(x & "­\x1­F")
Пример: ('a' & "­\x1­F") => 1 ; ('B' & "­\x1­F") => 2
Позиция большой буквы в алфавите (англ)
(x & '?') или (x ^ '@')
Пример: ('C' & '?') => 3 ; ('Z' ^ '@') => 26
Позиция строчной буквы в алфавите (англ)
(x ^ '')
Пример:
('d' ^ '') => 4 ; ('x' ^ '') => 24`
 

Десятичные дроби

Примеч­ание: хаки с float могут не работать на Ардуино! Разбить float в массив бит (unsigned uint32_t)
#include <st­din­t.h>
typedef union {float flt; uint32_t bits} lens_t;
uint32_t f2i(float x) {
  return ((lens_t) {.flt = x}).bits;
}
Вернуть массив бит обратно в float
float i2f(ui­nt32_t x) {
  return ((lens_t) {.bits = x}).flt;
}
Быстрый обратный квадратный корень
return i2f(0x­5f3­759df - f2i(x) / 2);
Быстрый nый корень из целого числа
float root(float x, int n) {
#DEFINE MAN_MASK 0x7fffff
#DEFINE EXP_MASK 0x7f800000
#DEFINE EXP_BIAS 0x3f800000
  uint32_t bits = f2i(x);
  uint32_t man = bits & MAN_MASK;
  uint32_t exp = (bits & EXP_MASK) - EXP_BIAS;
  return i2f((man + man / n) | ((EXP_BIAS + exp / n) & EXP_MA­SK));
}
Быстрая степень
return i2f((1 - exp) (0x3f8­00000 - 0x5c416) + f2i(x) exp)
Быстрый натура­льный логарифм
#DEFINE EPSILON 1.1920­928­955­078­125e-07
#DEFINE LOG2 0.6931­471­805­599453
return (f2i(x) - (0x3f8­00000 - 0x66774)) EPSILON LOG2
Быстрая экспонента
return i2f(0x­3f8­00000 + (uint3­2_t)(x * (0x800000 + 0x38aa­22)))
Примеч­ание: хаки с float могут не работать на Ардуино! Разбить float в массив бит (unsigned uint32_t)

Другое

Быстрая конвер­тация цвета R5G5B5 в R8G8B8
R8 = (R5 << 3) | (R5 >> 2)
G8 = (R5 << 3) | (R5 >> 2)
B8 = (R5 << 3) | (R5 >> 2)

Приоритет операций

Чтобы не плодить скобки, нужно знать приоритет операций
::
++
--
()
[]
.
->
++
--
+
-
!
~
(type)
*
&
sizeof
new, new[]
delete, delete[]
.*
->*
*
/
%
+
-
<<
>>
<
<=
>
>=
==
!=
&
^
|
&&
||
?:
=
+=
-=
*=
/=
%=
<<=
>>=
&=
^=
|=
Чтобы не плодить скобки, нужно знать приоритет операций

Приоритет операций

Чтобы не плодить скобки, нужно знать приоритет операций. В C++ он такой:
Приоритет операций
:: ++ -- () [] . -> ++ -- + - ! ~ (type) * & sizeof new, new[] delete, delete[] .* ->* * / % + - << >> < <= > >= == != & ^ | && || ?: = += -= *= /= %= <<= >>= &= ^= |=:: ++ -- () [] . -> ++ -- + - ! ~ (type) * & sizeof new, new[] delete, delete[] .* ->* * / % + - << >> < <= > >= == != & ^ | && || ?: = += -= *= /= %= <<= >>= &= ^= |=
   
 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

          arduino Cheat Sheet

          More Cheat Sheets by arest

          Kitty Keyboard Shortcuts