Битовые трюки

Сборники трюков #

• Bit Twiddling Hacks
• awesome-bits - урок ниже содержит в том числе и эти трюки в моём переводе
  • Перевод на русский от tproger

Целые числа #

Проверка на -1 #

В программировании очень часто встречаются инструменты, которые возвращают -1 в случае ошибки или "не найдено", т.е. валидным значением считается 0 и положительные числа. Чтобы не сравнивать значение с нулём, например if (val >= 0), можно использовать инверсию: в любом типе данных -1 это все биты - единички. Если инвертировать - получится ноль, if (~val) - проверка на >= 0:

String s = "abc";
if (~s.indexOf('b')) {
    // найдено
}

Заполнить битами #

((1ul << len) - 1) << from;

Заполняет len единичек, начиная с бита from, например ((1ul << 3) - 1) << 4 == 0b01110000.

Перемотка бита #

x = ((x >> 1) | (x << 7));

Перематывает за вызов один бит слева направо, то есть формирует последовательность 0b10000000, 0b01000000, 0b00100000, 0b00010000, 0b00001000, 0b00000100, 0b00000010, 0b00000001, 0b10000000, или 128, 64, 32, 16, 8, 4, 2, 1, 128.

Установка nго бита #

x | (1 << n);

Выключение nго бита #

x & ~(1 << n);

Инверсия nго бита #

x ^ (1 << n);

Округление до ближайшей степени двойки #

// работает только с 32 битными числами
uint32_t v;
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;

Умножение на 2 #

n << 1;

Деление на 2 #

n >> 1;

Умножение на mую степень двойки #

n << m;

Деление на mую степень двойки #

n >> m;

Остаток от деления #

n & 0b1;   // на 2 
n & 0b11;  // на 4 
n & 0b111; // на 8
// ...

Проверка равенства #

(a ^ b) == 0;

Проверка на кратность 2 #

(n & 1) == 1;

Обмен значениями #

a = a ^ b ^ (b = a);

Проверка на одинаковый знак #

(x ^ y) >= 0;

Смена знака #

i = ~i + 1;

i = (i ^ -1) + 1;

Вернёт 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 = n & ~(1 << (m - 1));

Проверить включен ли nый бит #

x & (1 << n)

Выделение самого правого включенного бита #

x & (-x);

Выделение самого правого выключенного бита #

~x & (x + 1);

Выделение правого включенного бита #

x | (x + 1);

Выделение правого выключенного бита #

x & (x - 1);

Получение отрицательного значения #

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

Поменять смежные биты #

((n & 10101010) >> 1) | ((n & 01010101) << 1);

Быстрый обратный квадратный корень #

float Q_rsqrt( float number ) {
  union {
    float f;
    uint32_t i;
  } conv = {number};
  conv.i = 0x5f3759df - ( conv.i >> 1 );
  conv.f *= 1.5 - number * 0.5 * conv.f * conv.f;
  return conv.f;
}

Быстрый квадратный корень (2 байта) #

uint16_t root2(uint16_t x) {
  uint16_t m, y, b;
  m = 0x4000;
  y = 0;
  while (m != 0) {
    b = y | m;
    y >>= 1;
    if (x >= b) {
      x -= b;
      y |= m;
    }
    m >>= 2;
  }
  return y;
}

Быстрый квадратный корень (4 байта) #

uint32_t root4(uint32_t x) {
  uint32_t m, y, b;
  m = 0x4000ul << 16;
  y = 0;
  while (m != 0) {
    b = y | m;
    y >>= 1ul;
    if (x >= b) {
      x -= b;
      y |= m;
    }
    m >>= 2ul;
  }
  return y;
}

Развернуть байт (11110000 -> 00001111) #

b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
b = (b & 0xAA) >> 1 | (b & 0x55) << 1;

Float числа #

Разбить в массив бит (unsigned uint32_t) #

typedef union {float flt; uint32_t bits} lens_t;

uint32_t f2i(float x) {
    return ((lens_t) {.flt = x}).bits;
}

Вернуть массив бит обратно в float #

float i2f(uint32_t x) {
    return ((lens_t) {.bits = x}).flt;
}

Быстрый обратный квадратный корень #

return i2f(0x5f3759df - 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_MASK));
}

Быстрая степень #

return i2f((1 - exp) * (0x3f800000 - 0x5c416) + f2i(x) * exp);

Быстрый натуральный логарифм #

#DEFINE EPSILON 1.1920928955078125e-07
#DEFINE LOG2 0.6931471805599453
return (f2i(x) - (0x3f800000 - 0x66774)) * EPSILON * LOG2;

Быстрая экспонента #

return i2f(0x3f800000 + (uint32_t)(x * (0x800000 + 0x38aa22)));

Строки #

Символ в число #

x & 0xf;
// '0' & 0xf == 0;
// '9' & 0xf == 9;

Байт в HEX #

char _encode(uint8_t b) {
    return (b < 10) ? (b + '0') : (b + 'a' - 10);
}

uint8_t b = 123;
char hex[2];
hex[0] = _encode(b >> 4);
hex[1] = _encode(b & 0xF);
// hex == "7b"

В нижний регистр #

(x | ' ');
// ('a' | ' ') == 'a';
// ('A' | ' ') == 'a';

В верхний регистр #

(x & '_');
// ('a' & '_') == 'A';
// ('A' & '_') == 'A';

Инвертировать регистр #

(x ^ ' ');
// ('a' ^ ' ') == 'A';
// ('A' ^ ' ') == 'a';

Позиция в алфавите (англ) #

(x & "\x1F");
// ('a' & "\x1F") == 1;
// ('B' & "\x1F") == 2;

Позиция большой буквы в алфавите (англ) #

(x & '?') или (x ^ '@');
// ('C' & '?') == 3;
// ('Z' ^ '@') == 26;

Позиция строчной буквы в алфавите (англ) #

(x ^ '`');
// ('d' ^ '`') == 4; 
// ('x' ^ '`') == 24;