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

Оглавление

Сборники трюков
Целые числа
Float числа
Строки

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

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

Целые числа #

builtin-функции #

У GCC/Clang есть несколько полезных функций, которые работают быстрее, чем написанные вручную конструкции (см. справочник):

__builtin_popcount(unsigned x) - количество установленных (1) бит в числе
__builtin_clz(unsigned x) - количество незначащих нулей (слева)
__builtin_ctz(unsigned x) - количество значащих нулей (справа)

У всех функций есть версии с окончанием на l для типа long и ll для long long, например __builtin_clzl, __builtin_ctzll.

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

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

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

Подсчёт бит (без цикла) #

uint8_t countBits8(uint8_t x) {
    x -= (x >> 1) & 0x55;
    x = (x & 0x33) + ((x >> 2) & 0x33);
    return (x + (x >> 4)) & 0x0F;
}

uint8_t countBits16(uint16_t x) {
    x -= (x >> 1) & 0x5555;
    x = (x & 0x3333) + ((x >> 2) & 0x3333);
    x = (x + (x >> 4)) & 0x0F0F;
    x = x + (x >> 8);
    return x & 0x1F;
}

uint8_t countBits32(uint32_t x) {
    x -= (x >> 1) & 0x55555555;
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x3F;
}

Подсчёт бит (цикл) #

uint8_t countBits(uint32_t x) {
    uint8_t count = 0;
    while (x) {
        x &= (x - 1);
        ++count;
    }
    return count;
}

Быстрый логарифм по 2 #

С округлением вниз, т.е. log2(31) == 4, log2(32) == 5:

uint8_t log2(uint32_t x) {
#if defined(__GNUC__)
  return x ? (31u - __builtin_clzl(x)) : 0;
#else
  uint8_t k = 0;
  while (x >>= 1) ++k;
  return k;
#endif
}

Среднее арифметическое #

// обычная версия
(x + y) >> 1;

// с защитой от переполнения суммы
((x ^ y) >> 1) + (x & y);

Мин/макс знаковое #

Определение минимального и максимального значения signed типа:

#define SIGNED_MIN(T) (-(1LL << (sizeof(T) * 8 - 1)))
#define SIGNED_MAX(T) ((1LL << (sizeof(T) * 8 - 1)) - 1)

//SIGNED_MIN(short);    -32768

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

((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 #

x && !(x & (x - 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);

Быстрое деление на 10 с остатком #

Примерно в 8 раз быстрее, чем val / 10 + val % 10. Можно использовать для разделения числа на десятичные разряды.

struct fdiv10_t {
    uint32_t quot;
    uint8_t rem;
};

fdiv10_t fdiv10(uint32_t num) {
    uint32_t quot = num >> 1;
    quot += quot >> 1;
    quot += quot >> 4;
    quot += quot >> 8;
    quot += quot >> 16;
    uint32_t qq = quot;
    quot >>= 3;
    uint8_t rem = uint8_t(num - ((quot << 1) + (qq & ~7ul)));
    if (rem > 9) rem -= 10, ++quot;
    return fdiv10_t{quot, rem};
}

fdiv10_t res = fdiv10(1234567);
// res.quot == 123456
// res.rem == 7

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

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;
}

Целочисленный квадратный корень 16 бит #

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

Выполняется 10 мкс (AVR) против 37 мкс sqrt (быстрее).

Целочисленный квадратный корень 32 бит #

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

Выполняется 46 мкс (AVR) против 38 мкс sqrt.

Целочисленный квадратный корень 64 бит #

uint32_t root64(uint64_t x) {
    uint64_t y = 0, m = 1ull << 62;

    while (m > x) m >>= 2;

    while (m != 0) {
        if (x >= y + m) {
            x -= y + m;
            y = (y >> 1) + m;
        } else {
            y >>= 1;
        }
        m >>= 2;
    }
    return y;
}

Выполняется 466 мкс (AVR) против 45 мкс sqrt.

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

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

Развернуть, 32 бит #

x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1);
x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2);
x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4);
x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8);
x = (x >> 16) | (x << 16);

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) {
    const uint32_t MAN_MASK = 0x7fffff;
    const uint32_t EXP_MASK = 0x7f800000;
    const uint32_t 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;

Полезные страницы #

Набор GyverKIT – наш большой стартовый набор Arduino, продаётся в России
Каталог ссылок на дешёвые Ардуины, датчики, модули и прочие железки с AliExpress
Обратная связь – сообщить об ошибке в уроке или предложить дополнение по тексту ([email protected])
Поддержать автора за работу над уроками

(1 голос)

Обновлено 19.01.2026

0 комментариев

Старые

Новые Популярные

Межтекстовые Отзывы

Посмотреть все комментарии