Тёмная сторона Си: трюки, хаки, магия и алгоритмы / forpes.ru

Главная
Тёмная сторона Си: трюки, хаки, магия и алгоритмы

Тёмная сторона Си: трюки, хаки, магия и алгоритмы +10

09.12.2025 08:05

DrArgentum 0 2100 Источник

Доброго времени суток, господа и дамы! Иногда у некоторых людей возникает желание заняться откровенным непотребством в программировании — то, что не несет практической пользы напрямую, но помогает развлечься. И я — не исключение. В этой статье я хочу рассказать вам о лайфхаках, трюках (магических и не очень), алгоритмах на языке C!

Идея написать эту статью зародилась из моего поста, после него я написал статью «Математика, биты, магия и немного ненормального программирования на C» и «Фокусы, хаки, магия и прочее ненормальное программирование на C», которые раскрывали много интересных моментов. Увидев, что многим понравилась, я задумался: почему бы не изучить еще какие-нибудь трюки, заодно практикуясь в программировании на C?

В этой статье будет еще больше всевозможных генераторов псевдослучайных чисел, гонок за скоростью и производительностью, алгоритмов, хаков и трюков!

Всех, кто заинтересовался — прошу под кат.

❯ Содержание

Вы можете читать статьи в любом порядке, они независимы друг от друга:

За две прошлые статьи мы разработали следующие алгоритмы:

fibonacci — вычисление n‑го числа Фибоначчи классическим итеративным методом
fib_golden_ratio — конвертация миль в километры через числа Фибоначчи с использованием формулы Бине
fib_golden_ratio_binary — улучшенная версия с использованием бинарного возведения в степень
fib_interpolate — конвертация миль в километры через интерполяцию чисел Фибоначчи
basic_miles2km — базовая конвертация миль в километры через умножение
binary_pow — бинарное возведение в степень для целых чисел
xorshift64 — быстрый генератор псевдослучайных чисел на основе сдвигов и XOR
rand_double — генерация случайного числа double в диапазоне [0.0, 1.0)
rand_range — генерация случайного числа в заданном диапазоне
xoshiro256pp — качественный генератор псевдослучайных чисел с 256‑битным состоянием
lehmer64 — быстрый генератор псевдослучайных чисел на основе линейного конгруэнтного метода
Q_rsqrt — быстрый вычисление обратного квадратного корня из Quake III
fastPow — быстрое приближенное вычисление степени через манипуляции с IEEE 754
fastestPow — ускоренная версия fastPow для float
div3 — быстрое деление на 3 через умножение и сдвиг
xor_swap — обмен значений двух переменных без временной переменной через XOR
count_trailing_zeros — подсчет младших нулевых битов через сдвиг
count_trailing_zeros_kernighan — подсчет младших нулевых битов через трюк Кернигана (x & -x)
pcg32 — современный качественный генератор псевдослучайных чисел
jenkins_mix — функция перемешивания из хеш‑алгоритма lookup3 Боба Дженкинса
is_power_of_two — быстрая проверка, является ли число степенью двойки
fast_mod — быстрое вычисление модуля для степеней двойки через битовую маску
Трюк Кернигана (x & -x) — выделение младшего установленного бита числа
Быстрая проверка на степень двойки — через x && !(x & (x - 1))
Быстрый обратный квадратный корень — знаменитый алгоритм из Quake III
Формула Бине — явная формула для вычисления чисел Фибоначчи
Бинарное возведение в степень — эффективный алгоритм возведения в степень

В этой статье мы продолжим эту серию статей, которая так понравилась многим.

Не буду долго тянуть, начинаем с алгоритма isqrt!

❯ ISQRT

Алгоритм isqrt выполняет вычисление целочисленного квадратного корня числа x. Это означает, что он находит наибольшее целое число res, такое что res * res <= x.

В отличие от Q_rsqrt, который мы разобрали в прошлой статье, который вычисляет обратный квадратный корень (1/sqrt(x)) с помощью магии чисел с плавающей точкой, этот алгоритм работает исключительно в целочисленной области, используя принцип бинарного поиска по битам.

uint32_t isqrt(uint32_t x) {
    uint32_t res = 0;
    uint32_t bit = 1 << 30;

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

    while (bit) {
        if (x >= res + bit) {
            x -= res + bit;
            res = (res >> 1) + bit;
        } else {
            res >>= 1;
        }
        bit >>= 2;
    }
    return res;
}

В начале мы создаем переменную res, хранящую в себе итоговый корень, изначально он равен нулю, а после задаем переменную bit — указатель, который будет перемещаться по битам результата. Начинаем с позиции 30. Вы можете задаться вопросом, почему не 32? Потому что квадрат числа с установленным 31 битом будет иметь порядок 2^62, что может выходить за рамки uint32_t.

Цикл while (bit > x) bit >>= 2; ищет старший значащий бит будущего корня. Он сдвигает переменную bit вправо на две позиции, пока bit не станет меньше или равен x. Если x маленькое (например, 100), нет смысла начинать проверку с бита 1<<30, таким образом мы быстро спускаемся до последнего до подходящего для x диапазона.

Цикл выполняется, пока наша маска bit не сдвинется в 0. На каждой итерации мы переходим к следующему биту, сдвигая bit на 2 позиции вправо (опять же, деление на 4).

Условие if (x >= res + bit) проверяет, достаточно ли велико оставшееся число x, чтобы «вместить» квадрат этого кандидата. Здесь используется математическая оптимизация: вместо прямого вычисления квадрата (res + bit)², что потребовало бы дорогой операции умножения, алгоритм использует инвариантное условие, которое позволяет выполнить проверку через простое сравнение и вычитание.

Инвариантное условие (инвариант) в программировании — это условие, которое остаётся неизменным на протяжении всего выполнения программы. Такими условиями могут быть значения переменных или определённая логика выполнения алгоритма.

❯ C++Sucks

Незатейливый, но прикольный трюк:

#include <stdio.h>

double m[] = {7709179928849219.0, 771};

int main() {
    m[1]-- ? m[0] *= 2, main() : printf((char*)m);
}

Данный код напишет он фразу «C++Sucks»!

Исходное число 7709179928849219.0 в двоичном представлении соответствует байтам строки «C++Sucks». Когда мы интерпретируем байты этого числа как символы, получается нужная фраза.

Функция main вызывает рекурсивно саму себя 771 раз, каждый раз удваивая первое магическое число. Удвоение в формате IEEE 754 это то же самое что и увеличение экспоненты на 1, что фактически сдвигает двоичное представление числа.

После 771 удвоения биты числа сдвигаются так, что занимают позиции, соответствующие ASCII‑кодам символов. Когда счетчик достигает нуля, программа выводит интерпретацию числа как строки символов.

❯ Код Грея

Код Грея, который носит также название зеркального, это двоичный код, в ко��ором две соседние кодовые комбинации различаются только цифрой в одном двоичном разряде. Иными словами, расстояние Хэмминга между соседними кодовыми комбинациями равно 1.

Зеркальным он называется из-за того, что первая половина значений при изменении порядка равна второй половине, за исключением старшего бита. Старший бит просто инвертируется. При делении каждой новой половины пополам это свойство сохраняется.

Пример кодов Грея порядка 2:

Его реализация на C представлена ниже:

uint32_t to_gray(uint32_t n) {
    return n ^ (n >> 1);
}

uint32_t from_gray(uint32_t gray) {
    gray ^= (gray >> 16);
    gray ^= (gray >> 8);
    gray ^= (gray >> 4);
    gray ^= (gray >> 2);
    gray ^= (gray >> 1);
    return gray;
}

Он основан на свойствах битовых операций, в частности XOR.

Преобразование в код Грея очень простое — число n сдвигается на один бит и выполняется XOR между исходным числом и сдвинутым. Для числа 5 (101 в двоичной) сдвиг дает 2 (010), XOR дает 111 (7), что является корректным кодом Грея для 5.

Обратное же сложнее, но использует ту же идею. Алгоритм последовательно применяет XOR с разными сдвигами для восстановления числа. Начинается с наибольшего сдвига (16 бит для 32 битного числа) и постепенно уменьшает сдвиг до 1 бита.

Использование побитовых сдвигов и XOR позволяет этому алгоритму быть невероятно быстрым. Сам алгоритм используют в микроконтроллерах, энкодерах, системах обработки сигналов, адресации цилиндром дисков.

❯ Counting Sort

Алгоритмы сортировки — неисчерпаемая тема. Давайте разберем специфичный метод сортировки массива — подсчетом для малых диапазонов.

void counting_sort_256(uint8_t *arr, size_t n) {
    size_t count[256] = {0};

    for (size_t i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    size_t idx = 0;
    for (size_t i = 0; i < 256; i++) {
        while (count[i]--) {
            arr[idx++] = i;
        }
    }
}

Данный алгоритм сортировки специфичен из‑за того что требуется знание ограниченного малого диапазона значений в одном массиве. Он работает через подсчет частоты встречаемости каждого возможного элемента с последующей реконструкцией отсортированного массива.

Временная сложность — O(n+k), где n — количество элементов в массиве, k — размер диапазона значений. Эффективность алгоритма напрямую зависит от соотношения между n и k — чем меньше диапазон k по сравнению с n, тем эффективнее работает алгоритм. Основное ограничение — алгоритм применим только для данных с известным ограниченным диапазоном целочисленных значений.

❯ ГПСЧ wyrand

Продолжим мою любимую тему — генераторы псевдослучайных чисел. Рассмотрим wyrand, алгоритм построенный на основе 128‑битной арифметики. Его работа основана на простой, но эффективной схеме перемешивания состояния.

uint64_t wyrand_state = 0xa55a5a5a5a5a5a5a; // Любое ненулевое начальное состояние

uint64_t wyrand() {
    wyrand_state += 0xa0761d6478bd642f;
    __uint128_t t = (__uint128_t)wyrand_state * (wyrand_state ^ 0xe7037ed1a0b428db);
    return (t >> 64) ^ t;
}

Инициализация начинается с установки константы состояния. На каждом шаге алгоритма к текущему состоянию прибавляется больше простое число, которое служит константой приращения.

Затем идет ключевая операция перемешивания, где текущее состояние умножается на его же версию, но которая прошла операцию XOR с другой магической константой 0xe7037ed1a0b428db. Умножение 64‑битных чисел с образованием 128‑битного результата эффективно перемешивает биты.

И под конец извлекается готовое псевдослучайное число путем применения операции XOR между старшей и младшей частями 128‑битного произведения. Таким образом wyrand невероятно быстрый, и проще чем PCG или xoshiro (которые были рассмотрены в ранних статьях).

❯ ГПСЧ MSWS

Раз уж пошла тема про ГПСЧ, грех будет не рассказать об алгоритме Middle‑Square weyl Sequence, предложенного легендарным Джоном фон Нейманом в 1940‑х годах.

uint64_t x = 0, w = 0;

uint32_t msws32() {
    x *= x;
    x += (w += 0xb5ad4eceda1ce2a9);
    return (x = (x >> 32)) | (x << 32);
}

Основной принцип заключается в том что используя два 64‑битных состояния (x и w) мы возводим x в квадрат (отсылка к классическому методу середины квадрата). Затем к результату добавляется обновляемое значение w, которое увеличвается на константу 0xb5ad4eceda1ce2a9 каждый вызов. Константа выбрана как произведение двух простых чисел для обеспечивания хорошего рассеивания.

Финальные преобразования выполняют циклический сдвиг на 32 бита, и возвращают младшие 32 бита результата.

MSWS относится к простейшим генераторам. Качество выходит достойным для многих некриптографических применений. Но при известном текущем предсказать следующее состояние не составляет трудности.

❯ ГПСЧ RomuDuo

Очень быстрый генератор и экзотический из семейства Romu, идеален для симуляций. Использует умножение и сдвиги.

uint64_t romu_duo_state1 = 0x1234567890abcdef;
uint64_t romu_duo_state2 = 0xfedcba0987654321;

uint64_t romu_duo() {
    uint64_t xp = romu_duo_state1;
    romu_duo_state1 = 15241094284759029579u * romu_duo_state2;
    romu_duo_state2 = romu_duo_state2 - xp;
    romu_duo_state2 = (romu_duo_state2 << 32) | (romu_duo_state2 >> 32);
    return xp;
}

Алгоритм работает по принципу чередования арифметических операций и битовых сдвигов.

Алгоритм использует два 64‑битных состояния, и на каждом шаге выполняется сохранение текущего хранения в переменную xp, которая позже станет возвращаемым случайным числом. Дальше идет умножение на большое простое число, после умножения модифицируется вычитанием, а в завершении циклический сдвиг на 32 бита. Это перемещает старшие 32 бита на место младших и наоборот.

❯ Бонус!

Давайте разбавим статью бонусным фокусом — быстрый логарифм по степени 2.

Например, быстрый логарифм по степени 2:

int popcount(uint32_t x) {
    int count = 0;
    while (x) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

int log2_32(uint32_t x) {
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return popcount(x - 1);
}

Первая фаза функции log2_32 это превращение числа в такую форму, где все биты младше старшего установленного бита становятся равными 1.

Дальше идет функция popcount — это функция, которая подсчитывает количество установленных битов (битов со значением 1) в двоичном представлении числа.

Второй этап — вычисление результата через popcount(x - 1). После первого этапа мы получаем число вида 2ⁿ - 1, где n — позиция старшего бита плюс один. Вычитая единицу, мы получаем число, в котором установлено ровно n битов. Функция popcount подсчитывает количество этих битов, что и даёт нам значение двоичного логарифма.

❯ Бенчмарки

Самое сладкое! Давайте скомбинируем старые бенчмарки с новыми и посмотрим на итоги нашей работы.

PRNG Performance (10,000,000 iterations):
-----------------------------------------
xorshift64:      15.31 ms  (652.97M numbers/s)
lehmer64:        21.34 ms  (468.57M numbers/s)
xoshiro256pp:    16.12 ms  (620.18M numbers/s)
pcg32:           14.07 ms  (710.60M numbers/s)
wyrand:          18.06 ms  (553.85M numbers/s)
msws32:          17.99 ms  (555.97M numbers/s)
romu_duo:        14.21 ms  (703.78M numbers/s)
-----------------------------------------

Conversion Methods Performance (each method called 10000 times per point):
----------------------------------------------------------------------
Basic                    :     0.23 ms  ( 0.001 us/call)
Fibonacci Interpolation  :     1.58 ms  ( 0.008 us/call)
Fibonacci Cache          :     1.40 ms  ( 0.007 us/call)
Golden Ratio             :    17.02 ms  ( 0.085 us/call)
Golden Ratio (Binary)    :     3.54 ms  ( 0.018 us/call)
----------------------------------------------------------------------

Accuracy Comparison (5 sample points):
Miles |   Basic   | Interpol |  Cache   |  Golden  | GoldenBin
------+-----------+----------+----------+----------+-----------
    5 |      8.05 |    0.58% |    0.58% |    0.58% |    0.58%
   30 |     48.28 |    0.53% |    0.53% |    0.53% |    0.53%
   55 |     88.51 |    0.55% |    0.55% |    0.55% |    0.55%
   80 |    128.75 |    0.54% |    0.54% |    0.54% |    0.54%
  100 |    160.93 |    0.54% |    0.54% |    0.54% |    0.54%
---------------------------------------------------------------

Math Algorithms Performance (1000000 iterations):
--------------------------------------------
fast_pow:                1.41 ms  ( 0.001 us/call)
fastest_pow:             1.32 ms  ( 0.001 us/call)
fast_mod:                1.70 ms  ( 0.002 us/call)
is_power_of_two:         1.46 ms  ( 0.001 us/call)
jenkins_hash:           30.17 ms  ( 0.030 us/call)
jenkins_mix+final:      29.34 ms  ( 0.029 us/call)
xor_swap:                2.21 ms  ( 0.002 us/call)
div3:                    1.13 ms  ( 0.001 us/call)
isqrt:                   6.12 ms  ( 0.006 us/call)
to_gray:                 1.16 ms  ( 0.001 us/call)
from_gray:               1.37 ms  ( 0.001 us/call)
counting_sort_256:       7.58 ms  ( 0.758 us/call)
--------------------------------------------

Если вы хотите посмотреть на графики, вот они:

В итоге лидерами среди ГПСЧ по скорости оказываются pcg32, romu_duo и xorshift64. В средней группе msws32, xoshiro256pp, wyrand. А самым медленным стал lehmer64.

❯ Заключение

Спасибо за прочтение статьи! Я надеюсь, вы узнали что‑то новенькое, или может, какой‑нибудь трюк натолкнул вас на другой интересный алгоритм. Если нашли нюанс в самой статье — пишите в комментарии.

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

Примеры работы кода вы можете увидеть в моем репозитории The Art Of Fun C.

❯ Источники

Коды Грея и задачи перебора

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩