Доброго времени суток, господа и дамы! Иногда у некоторых людей возникает желание заняться откровенным непотребством в программировании — то, что не несет практической пользы напрямую, но помогает развлечься. И я — не исключение. В этой статье я хочу рассказать вам о лайфхаках, трюках (магических и не очень) и алгоритмах на языке C!
Идея написать эту статью зародилась из моего поста, после него я начал серию статей, которая раскрывала много интересных моментов — от математических алгоритмов и оптимизации до ГПСЧ.
Если вы видите эту статью, значит еще не все тайны C раскрыты. В этой статье будет еще больше свежих хаков, фанов, трюков, еще больше магии и скорости! А также нетипичных алгоритмов и структур данных, что позволит вам почерпнуть и полезную информацию тоже!
Добро пожаловать в новую часть. Прошу под кат — там будет жарко, быстро и очень, очень интересно.
❯ Содержание
Вы можете читать статьи в любом порядке, они независимы друг от друга:
«Математика, биты, магия и немного ненормального программирования на C»
«Фокусы, хаки, магия и прочее ненормальное программирование на C»
«Непотребные алгоритмы, ненормальные трюки и всевозможные хаки на C»
❯ Алгоритм bitboard для шахмат/игр
Использование 64-битных чисел для игрового поля — классика оптимизации.
#include <stdio.h> #include <stdint.h> typedef uint64_t Bitboard; Bitboard knights_attacks(Bitboard knights) { Bitboard l1 = (knights >> 1) & 0x7F7F7F7F7F7F7F7F; Bitboard l2 = (knights >> 2) & 0x3F3F3F3F3F3F3F3F; Bitboard r1 = (knights << 1) & 0xFEFEFEFEFEFEFEFE; Bitboard r2 = (knights << 2) & 0xFCFCFCFCFCFCFCFC; return (l1 | r1) << 16 | (l1 | r1) >> 16 | (l2 | r2) << 8 | (l2 | r2) >> 8; } void print_bitboard(Bitboard bb) { for (int row = 7; row >= 0; row--) { for (int col = 0; col < 8; col++) {3 int square = row * 8 + col; printf("%c ", (bb >> square) & 1 ? '1' : '.'); } printf("\n"); } printf("\n"); } int main() { Bitboard knight = 1ULL << 36; /* конь на e4*/ printf("позиция коня:\n"); print_bitboard(knight); printf("возможные ходы коня:\n"); Bitboard attacks = knights_attacks(knight); print_bitboard(attacks); return 0; }
Фанфакт: в английском как шахматная фигура конь это не horse, а knight. Ладья — Rook (грач/утес/башня). Слон — Bishop (епископ).
Функция knights_attacks вычисляет все возможные ходы коня за несколько битовых операций. Принцип такой: конь ходит буквой «Г» — на две клетки в одном направлении и одну в перпендикулярном.
Алгоритм делает сдвиги в четыре стороны. Сначала сдвигает позиции коней влево и вправо на 1 и 2 клетки (l1, r1, l2, r2). Маски 0x7F... и 0xFE... нужны чтобы не было «перетекания» битов через края доски — они отсекают боковые столбцы.
Затем комбинируем эти сдвиги. Объединение l1 и r1 дает горизонтальные смещения на одну клетку. Сдвиг этой комбинации на 16 рядов вверх и вниз дает вертикальное смещение на две клетки — получаем ходы типа «две вверх/вниз, одна вбок». Аналогично l2 и r2 дают смещение на две клетки по горизонтали. Сдвиг на 8 рядов дает смещение на одну клетку по вертикали — это ходы «одна вверх/вниз, две вбок».
Битовое ИЛИ всех четырех вариантов дает полную маску атак.
Главная прелесть — всего 10 битовых операций для любого количества коней на доске. Вместо перебора 64 клеток или циклов по фигурам — мгновенный расчет. Именно так работают современные шахматные движки.
При запуске мы получаем такой красивый вывод:
позиция коня: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . возможные ходы коня: . . . . . . . . . . . 1 . 1 . . . . 1 . . . 1 . . . . . . . . . . . 1 . . . 1 . . . . 1 . 1 . . . . . . . . . . . . . . . . . .
❯ Неточное сравнение дробных чисел
Алгоритм решает проблему неточного сравнения чисел с плавающей точкой. Прямое сравнение через == часто даёт ложный результат из-за особенностей двоичного представления и накопления ошибок округления.
bool fuzzy_float_eq(float a, float b) { float abs_diff = fabsf(a - b); float max_abs = fmaxf(fabsf(a), fabsf(b)); return abs_diff <= max_abs * 1e-6f || abs_diff < 1e-12f; }
Работает функция вот так: сначала вычисляется абсолютная разница между числами. Затем определяется максимальное по модулю из двух чисел. Основная проверка использует два условия. Первое — относительная погрешность: абсолютная разница не превышает одной миллионной от максимального модуля. Это покрывает большинство случаев. Второе — абсолютная погрешность: разница меньше фиксированного малого значения, что нужно для корректной работы с числами, близкими к нулю, где относительная погрешность теряет смысл.
int main() { float num1 = 1.0000009901f; float num2 = 1.0000009902f; if (fuzzy_float_eq(num1, num2)) { printf("Числа считаются равными\n"); } else { printf("Числа различны\n"); } return 0; }
Но так как это нечеткое сравнение, данный код выдаст что числа num1 и num2 равные. По сути, суть алгоритма в том, что числа считаются равными, если они либо очень близки относительно их величины, либо отличаются на исчезающе малую величину.
❯ ГПСЧ GJF (Gonzalo Joseph’s Fast)
В этой серии статьи мы давно не затрагивали тему ГПСЧ!
#include <stdint.h> uint64_t gjf_state[2] = {0x123456789ABCDEF, 0xFEDCBA987654321}; uint64_t gjf64(void) { uint64_t s0 = gjf_state[0]; uint64_t s1 = gjf_state[1]; gjf_state[0] = s1; s0 ^= s0 << 23; gjf_state[1] = s0 ^ s1 ^ (s0 >> 17) ^ (s1 >> 26); return gjf_state[1] + s1; }
Это компактный и ⚡ blazingly fast ⚡ (и даже не надо переписывать на раст) генератор, который хранит состояние в двух 64-битных переменных. В основе — перестановка и смешивание битов через сдвиги и XOR.
Его работа основана на быстрых битовых операциях: сдвигах и XOR. В начале функции сохраняются текущие значения состояния в локальные переменные s0 и s1. Первое состояние обновляется простой перестановкой — оно становится равным старому второму состоянию.
Затем начинается перемешивание. Значение s0 подверг��ется операции XOR'а с собственной копией, сдвинутой влево на 23 бита. Этот этап вносит нелинейность и распространяет изменение битов. После этого вычисляется новое значение для второго элемента состояния. Оно представляет собой XOR четырёх компонентов: только что изменённого s0, старого s1, а также сдвинутых вправо на 17 бит версии s0 и на 26 бит версии s1. Такая комбинация сдвигов разной длины обеспечивает тщательное перемешивание битов со всего 128-битного пространства состояния.
Финальный шаг — генерация выходного числа. Функция возвращает сумму только что вычисленного нового второго состояния и старого значения s1. Это сложение улучшает статистические свойства вывода, делая распределение более равномерным. Весь цикл выполняется за несколько тактов процессора, что делает генератор одним из самых быстрых в своём классе. Его период огромен, а качества случайности достаточно для большинства симуляций, игр и задач, не требующих криптографической стойкости.
Давайте посмотрим на пример:
int main() { for (int i = 0; i < 5; i++) { printf("%016llx\n", gjf64()); } return 0; }
И код выдаст следующие шестнадцатеричные числа:
ccf7ce0251e21edb 232e19416e19e115 5d6f795c479bf4d2 dc8a1592370d6141 10e2fc8d1d6cc6f0
В этом коде значение стартового состояния предопределено, но вы можете реализовать генерацию сида.
❯ XXTEA — крошечный блочный шифр
Компактный и эффективный шифр для эмбединга, осдева или прочих ваших странных потребностей. XXTEA шифрует массив 32-битных слов налету, используя ключ из 4 слов. Алгоритм выполняет несколько раундов, на каждом смешивая данные с ключом через XOR, сдвиги и сложение.
#include <stdint.h> #define DELTA 0x9e3779b9 #define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z))) void xxtea_encrypt(uint32_t *v, int n, uint32_t const key[4]) { uint32_t y, z, sum; unsigned p, rounds, e; if (n < 1) return; rounds = 6 + 52/n; sum = 0; z = v[n-1]; do { sum += DELTA; e = (sum >> 2) & 3; for (p=0; p<n-1; p++) { y = v[p+1]; z = v[p] += MX; } y = v[0]; z = v[n-1] += MX; } while (--rounds); }
Первое, что делает алгоритм — вычисляет число раундов. Формула 6 + 52/n гарантирует, что даже для больших массивов будет выполнено достаточное количество перемешиваний. Начинается цикл с обнулённой переменной sum.
В каждом раунде к sum прибавляется число DELTA. Затем определяется e — индекс для выбора слова ключа, основанный на текущей сумме.
Далее идёт сердце алгоритма — внутренний цикл по всем словам массива, кроме последнего. Для каждого слова вычисляется замысловатая функция MX. В ней через сдвиги, сложения и XOR перемешиваются соседние слова (y и z), текущая сумма и часть ключа. Результат этого микса прибавляется к текущему слову, что и является шифрованием.
После обработки основного массива отдельно шифруется последнее слово с первым, и раунд завершается. Этот процесс повторяется заданное количество раундов, постепенно и необратимо перемешивая все данные с ключом.
void xxtea_decrypt(uint32_t *v, int n, uint32_t const key[4]) { uint32_t y, z, sum; unsigned p, rounds, e; if (n < 1) return; rounds = 6 + 52/n; sum = rounds * DELTA; y = v[0]; do { e = (sum >> 2) & 3; for (p=n-1; p>0; p--) { z = v[p-1]; y = v[p] -= MX; } z = v[n-1]; y = v[0] -= MX; sum -= DELTA; } while (--rounds); }
Ну и также покажу функцию для дешифровки, ключевое отличие в обратном порядке операций и направлении. Если шифрование идёт «вперёд», то дешифрование идёт «назад», отменяя каждый шаг. Начальное значение sum не ноль, а rounds * DELTA — полная сумма, которая накопилась бы к концу шифрования. Важно понимать, что порядок обновления переменных y и z в дешифровании обратный по отношению к шифрованию, чтобы гарантировать, что при вычислении MX используются те же значения, что и при шифровании.
Ну и на примере демонстрация работы:
int main() { uint32_t data[] = {0x12345678, 0x9ABCDEF0}; uint32_t key[4] = {0xA1B2C3D4, 0x5E6F7A8B, 0x9C0D1E2F, 0x3A4B5C6D}; printf("Original: 0x%08X 0x%08X\n", data[0], data[1]); xxtea_encrypt(data, 2, key); printf("After encrypt: 0x%08X 0x%08X\n", data[0], data[1]); xxtea_decrypt(data, 2, key); printf("After decrypt: 0x%08X 0x%08X\n", data[0], data[1]); return 0; }
С таким вот выводом:
Original: 0x12345678 0x9ABCDEF0 After encrypt: 0xB9F221ED 0x71F80F5B After decrypt: 0x12345678 0x9ABCDEF0
Если кому то надо, то на моей системе такой результат времени запуска бинарника:
Original: 0x12345678 0x9ABCDEF0 After encrypt: 0xB9F221ED 0x71F80F5B After decrypt: 0x12345678 0x9ABCDEF0 ________________________________________________________ Executed in 3.96 millis fish external usr time 1.09 millis 1.09 millis 0.00 millis sys time 2.89 millis 1.02 millis 1.87 millis
❯ Прямой доступ к битам дробного числа
В языке C нет прямого способа посмотреть битовое представление числа с плавающей запятой. Трюк в том, чтобы заставить память интерпретироваться по-разному. Для этого используется union — область памяти, в которой данные разных типов хранятся по одному и тому же адресу.
#include <stdio.h> #include <stdint.h> typedef union { float f; struct { uint32_t mantissa : 23; uint32_t exponent : 8; uint32_t sign : 1; } bits; } float_cast; int main() { float_cast fc; fc.f = -3.14f; printf("Number: %f\n", fc.f); printf("Sign: %u\n", fc.bits.sign); printf("Exponent: %u\n", fc.bits.exponent); printf("Mantissa: 0x%06X\n", fc.bits.mantissa); return 0; }
Объявляется union с именем float_cast. Внутри него два поля: обычное число float f и структура bits. Они занимают один и тот же участок памяти размером 4 байта (32 бита). Когда мы записываем значение в fc.f, биты сразу располагаются в соответствии со стандартом IEEE 754. Через структуру bits мы получаем доступ к этим же битам, но уже как к отдельным именованным полям: знак (1 бит), порядок (8 бит) и мантисса (23 бита). Это не создаёт копии и не конвертирует данные — это просто другая «маска» для просмотра тех же битов.
Порядок полей в структуре зависит от архитектуры. В данном случае предполагается, что знаковый бит находится в старшем разряде.
Number: -3.140000 Sign: 1 Exponent: 128 Mantissa: 0x48F5C3
❯ Свертка массива XOR-ом для быстрой проверки изменений
Код выполняет быструю свёртку (контрольную сумму, checksum) массива данных с помощью операции XOR. Он создаёт короткий «отпечаток» массива, который резко меняется при любом изменении входных данных.
Главный принцип алгоритма в его чувствительности к изменениям. Изменится хотя бы один бит в любом элементе массива — и итоговый хэш, скорее всего, будет совершенно другим. Это делает метод идеальным для быстрой проверки целостности данных в памяти или при простом обмене, где не нужна криптографическая стойкость. Скорость работы очень высока, так как это всего один проход по данным с минимальной арифметикой.
#include <stdio.h> #include <stdint.h> uint32_t xor_fold(const uint32_t* data, size_t len) { uint32_t result = 0; for (size_t i = 0; i < len; i++) result ^= data[i]; return result; } int main() { uint32_t array1[] = {0x12345678, 0x9ABCDEF0, 0x13579BDF}; uint32_t array2[] = {0x12345678, 0x9ABCDEF0, 0x13579BDF}; uint32_t array3[] = {0x12345678, 0x9ABCDEF0, 0x13579BDE}; printf("Hash array1: %08X\n", xor_fold(array1, 3)); printf("Hash array2: %08X\n", xor_fold(array2, 3)); printf("Hash array3: %08X\n", xor_fold(array3, 3)); return 0; }
И вот такой вот вывод:
Hash array1: 9BDF1357 Hash array2: 9BDF1357 Hash array3: 9BDF1356
Он не заменит криптографический хэш, но отлично справляется с задачей быстрого обнаружения различий в блоках данных.
❯ ГПСЧ Tyche
Tyche — это вариация генератора Xorshift с 128-битным состоянием (мы его уже рассматривали в прошлой статье). Алгоритм использует сдвиги и XOR для перемешивания. Инициализация выполняет «прогрев» генератора (20 пустых итераций) для улучшения начального состояния. Генератор быстр и подходит для симуляций.
#include <stdio.h> #include <stdint.h> #include <time.h> typedef struct { uint32_t a, b, c, d; } TycheState; uint32_t tyche_next(TycheState *s) { uint32_t t = s->b; s->b = s->c; s->c = s->d; s->a = (s->a ^ (s->a << 11)) ^ (t ^ (t >> 19)); s->d = s->a ^ s->b ^ s->c; return s->d; } void tyche_init(TycheState *s, uint32_t seed) { s->a = 0x6C078965 * (seed ^ (seed >> 30)) + 1; s->b = s->a + 0x6C078965; s->c = s->b + 0x6C078965; s->d = s->c + 0x6C078965; for (int i = 0; i < 20; i++) { tyche_next(s); } }
Ключевая структура — TycheState. Это сердце генератора, где хранится его 128-битное состояние в виде четырёх 32-битных целых чисел: a, b, c, d.
Алгоритм работает в два этапа. Первый — инициализация в tyche_init. Она превращает один сид в начальное состояние из четырёх чисел. Используется умножение на константу и XOR для рассеивания битов. После этого генератор «прогревается» 20 холостыми тактами, чтобы устранить возможные корреляции, если начальное зерно было таким себе.
Второй этап — генерация нового числа в tyche_next. Это и есть вариация Xorshift. Алгоритм выполняет быструю перестановку: b, c, d сдвигаются, а значение a интенсивно перемешивается с использованием сдвигов и операции XOR с предыдущим значением b. Новое значение d (которое и возвращается) вычисляется как XOR всех трёх обновлённых регистров состояния. Весь процесс крайне быстр, требует лишь несколько битовых операций на процессоре.
И давайте реализуем пример работы:
int main() { TycheState rng; tyche_init(&rng, time(NULL)); printf("рандомные 16битные числа:\n"); for (int i = 0; i < 10; i++) { printf("0x%08X\n", tyche_next(&rng)); } printf("\nВ диапазоне 0..99:\n"); for (int i = 0; i < 10; i++) { printf("%d ", tyche_next(&rng) % 100); } printf("\n"); return 0; }
С вот таким выводом у меня:
рандомные 16битные числа: 0xF01D2505 0x71012006 0xE0182024 0x21292603 0x81310620 0x00002403 0xC0210425 0x81302026 0x88000000 0x89200004 В диапазоне 0..99: 38 20 16 84 72 61 80 52 44 65
❯ Заключение
Спасибо за прочтение статьи! Я надеюсь, вы узнали что‑нибудь новенькое, или, может быть, какой‑нибудь трюк натолкнул вас на другой интересный алгоритм. Если нашли нюанс в самой статье — пишите в комментарии.
Девятая часть получилась насыщенной: от сортировок и криптографии до битовой магии и математических трюков.
Если вам понравился изложенный материал, могу предложить вам подписаться на мой блог в телеграме. Если, конечно, вам статья понравилась и вы хотите видеть чуть больше.
Примеры работы кода вы м��жете увидеть в моем репозитории The Art Of Fun C.
Перед оплатой в разделе «Бонусы и промокоды» в панели управления активируйте промокод и получите кэшбэк на баланс.
