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

Идея написать эту статью зародилась из моего поста, после него я начал серию статей, которая раскрывала много интересных моментов — от математических алгоритмов и оптимизации до ГПСЧ.

Если вы видите на экране эту шестую часть нашей бесконечной саги о ненормальном программировании на C, значит, мы с вами прошли уже немало: от конвертации миль в километры через Фибоначчи до ГПСЧ и быстрых вычислений.

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

Добро пожаловать в шестую часть. Прошу под кат — там будет жарко, быстро и очень, очень интересно.

Мы вместе спускались в кроличью нору, и каждый раз казалось, что вот оно — дно, но неожиданно со дна стучались. Си — невероятно простой и сложный язык одновременно.

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

Но на этом наша история не заканчивается. Впереди нас ждут структуры данных, алгоритмы сжатия, ГПСЧ и настолько бесполезные трюки, что их полезность становится философским вопросом.

❯ Расстояние Левенштейна

Начну с простого, но интересного алгоритма.

Расстояние Левенштейна — метрика, измеряющая по модулю разность между двумя последовательностями символов. Определяется как минимальное количество односимвольных операций (вставки, удаления, замены), необходимых для превращения одной последовательности символов в другую.

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

#include <stdlib.h>
#include <string.h>

static inline int min2(int a, int b) {
    return a < b ? a : b;
}

static inline int min3(int a, int b, int c) {
    return min2(a, min2(b, c));
}

int levenshtein(const char* s1, const char* s2) {
    if (!s1 || !s2) {
        return -1;
    }

    size_t n = strlen(s1);
    size_t m = strlen(s2);

    if (n == 0) {
        return (int)m;
    }
    if (m == 0) {
        return (int)n;
    }

    if (n > m) {
        const char* tmp = s1;
        s1 = s2;
        s2 = tmp;
        size_t t = n;
        n = m;
        m = t;
    }

    int* buffer = (int*)malloc(2 * (n + 1) * sizeof(int));
    if (!buffer) {
        return -1;
    }

    int* prev = buffer;
    int* curr = buffer + (n + 1);

    for (size_t i = 0; i <= n; i++) {
        prev[i] = (int)i;
    }

    for (size_t j = 1; j <= m; j++) {
        curr[0] = (int)j;

        const char s2_char = s2[j - 1];
        
        for (size_t i = 1; i <= n; i++) {
            int cost = (s1[i - 1] == s2_char) ? 0 : 1;
            curr[i] = min3(prev[i] + 1, curr[i - 1] + 1, prev[i - 1] + cost);
        }

        int* tmp = prev;
        prev = curr;
        curr = tmp;
    }

    int result = prev[n];
    free(buffer);
    return result;
}

В начале функция обрабатывает тривиальные случаи, когда одна из строк пуста. Затем, чтобы оптимизировать использование памяти, строки переставляются, гарантируя, что первая строка s1 является более короткой. Вместо хранения всей матрицы размером (n+1) × (m+1) алгоритм использует только два одномерных массива длиной (n+1), что значительно сокращает потребление памяти.

Алгоритм заполняет первый массив базовыми значениями. Затем для каждого символа j второй строки s2 он вычисляет новую строку матрицы в массиве curr. Для каждого символа i первой строки s1 вычисляется стоимость трех возможных операций: удаление (стоимость из предыдущей строки + 1), вставка (стоимость из текущей строки + 1) и замена или совпадение (стоимость из предыдущей диагонали + 0 или 1). Из этих трех вариантов выбирается минимальная стоимость. После обработки всех символов s1 массивы prev и curr меняются местами для следующей итерации.

После завершения циклов результат — минимальная стоимость редактирования — хранится в prev[n]. Память освобождается, и значение возвращается.

❯ ГПСЧ MurmurHash3

MurmurHash3 — это некриптографическая хеш-функция, созданная для хеш-таблиц.

В нашем случае алгоритм адаптирован для создания ГПСЧ. Вместо хеширования данных, функция хеширует счетчик с использованием сида. Это создает детерминированную последовательность чисел с хорошими статистическими свойствами.

typedef struct {
    uint64_t seed;
    uint64_t counter;
} murmur3_prng_t;

static inline uint64_t rotl64(uint64_t x, int8_t r) {
    return (x << r) | (x >> (64 - r));
}

static inline uint64_t fmix64(uint64_t k) {
    k ^= k >> 33;
    k *= 0xff51afd7ed558ccdULL;
    k ^= k >> 33;
    k *= 0xc4ceb9fe1a85ec53ULL;
    k ^= k >> 33;
    return k;
}

void murmur3_prng_init(murmur3_prng_t *prng, uint64_t seed) {
    prng->seed = seed;
    prng->counter = 0;
}

uint64_t murmur3_prng_next(murmur3_prng_t *prng) {
    uint64_t h1 = prng->seed;
    uint64_t k1 = prng->counter++;

    const uint64_t c1 = 0x87c37b91114253d5ULL;
    const uint64_t c2 = 0x4cf5ad432745937fULL;

    k1 *= c1;
    k1 = rotl64(k1, 31);
    k1 *= c2;

    h1 ^= k1;
    h1 = rotl64(h1, 27);
    h1 = h1 * 5 + 0x52dce729;

    h1 ^= 4;
    h1 = fmix64(h1);

    return h1;
}

Структура murmur3_prng_t содержит сид и counter (счётчик, инкрементируемый при каждом вызове). Функция rotl64 делает циклический сдвиг влево, fmix64 выполняет финальное перемешивание битов.

Генератор инициализируется функцией murmur3_prng_init, задающей сид и обнуляющей счётчик. Основная функция murmur3_prng_next генерирует очередное случайное число: берёт текущий счётчик, умножает на константы c1 и c2, делает циклические сдвиги, затем комбинирует с сидом через XOR. После этого применяются дополнительные преобразования — сдвиг, умножение на 5 плюс константа, объединение с числом 4 и финальное перемешивание fmix64.

❯ Просмотр адресов функций на C

Программа извлекает и показывает адрес функции в памяти. Можно сказать, что это некий «dma bypass» (программный метод обхода защитных механизмов).

unsigned char* unwrap(void (*fn)()) {
    static unsigned char buffer[sizeof(fn)];
    memcpy(buffer, fn, sizeof(fn));
    return buffer;
}

void bar() {};

int main() {
    volatile unsigned char* icall_w = unwrap(bar);

    printf("code: ");

    for (int i = 0; i < sizeof(icall_w); i++) {
        printf("%02x ", (unsigned char)icall_w[i]);
    }

    printf("\n");
    return 0;
}

Вся суть в функции unwrap. Она получает указатель на функцию (проще говоря — её адрес в памяти), копирует этот адрес в байтовый массив и возвращает его. Важный момент: sizeof(fn) — это размер указателя (4 или 8 байт), а не размер кода самой функции. Поэтому копируется только адрес, а не инструкции функции. В главной функции мы передаём адрес функции bar в unwrap. Получаем массив байтов, который и есть этот самый адрес. Затем программа просто выводит эти байты в шестнадцатеричном виде.

Что выводится на самом деле? Не код функции, а её местоположение в памяти. Этот адрес будет меняться при каждом запуске (из‑за ASLR — защиты операционной системы), и порядок байтов в выводе зависит от архитектуры процессора.

Например, у меня вывод следующий:

code: c3 66 66 2e 0f 1f 84 00

❯ Вычисление числа π через ряд Лейбница

Что? Да! Алгоритм Лейбница — это один из самых простых способов получить π, хотя и не самый быстрый. Формула выглядит так: π/4 = 1 – 1/3 + 1/5 – 1/7 + 1/9 – ... и так до бесконечности. Знаки чередуются, а в знаменателе стоят нечётные числа. Чем больше слагаемых мы посчитаем, тем точнее будет результат. В конце это всё умножается на 4, чтобы получить само π.

#include <omp.h>

double calculate_pi_leibniz(long long iterations) {
    double pi = 1.0;
    long long i;
    int sign = -1;

    #pragma omp parallel for reduction(+:pi) private(sign)
    for (i = 1; i < iterations; i++) {
        sign = (i % 2 == 0) ? 1 : -1;
        pi += sign / (2.0 * i + 1.0);
    }

    return pi * 4;
}

int main(int argc, char *argv[]) {
    long long iterations = 1000000000;
    if (argc > 1) {
        iterations = atoll(argv[1]);
    }

    double start_time = omp_get_wtime();
    double pi = calculate_pi_leibniz(iterations);
    double end_time = omp_get_wtime();

    printf("π = %.15f\n", pi);
    printf("Iters: %lld\n", iterations);
    printf("Time: %.3f seconds\n", end_time - start_time);

    return 0;
}

OpenMP здесь ускоряет вычисления, распараллеливая цикл на несколько ядер процессора. Все потоки считают свою часть суммы, а потом результаты объединяются в один. Без этого работа шла бы только на одном ядре и дольше.

Вот такой вывод получился у меня при -O2:

π = 3.141592652589449
Iters: 1000000000
time: 0.160 seconds

❯ Безусловное вычисление минимума/максимума

Через битовые трюки можно находить минимум и максимум целых двух чисел без плебейских операторов ветвления! Основная идея — использование битовых масок вместо условных переходов, что теоретически может ускорить выполнение за счёт устранения предсказания переходов процессором.

int min_no_branch(int x, int y) {
    return y ^ ((x ^ y) & -(x < y));
}

int max_no_branch(int x, int y) {
    return x ^ ((x ^ y) & -(x < y));
}

int min_quick(int x, int y) {
    int diff = x - y;
    return y + (diff & (diff >> (sizeof(int) * CHAR_BIT - 1)));
}

int max_quick(int x, int y) {
    int diff = x - y;
    return x - (diff & (diff >> (sizeof(int) * CHAR_BIT - 1)));
}

Первые две функции (min_no_branch/max_no_branch) создают маску: -(x < y) дает 0xFFFFFFFF (все биты 1) если x < y, и 0 если нет. Этой маской выбираются нужные биты через XOR. Например, min_no_branch считает y ^ ((x ^ y) & mask). Если x < y (маска 0xFFFFFFFF), это упрощается до x. Иначе — до y.

Вторые две функции (min_quick/max_quick) работают через разность diff = x – y. Знаковый бит diff сдвигается вправо на (размер int в битах – 1), создавая такую же маску (0xFFFFFFFF если diff отрицателен, т. е. x < y, иначе 0). Для минимума: y + (diff & mask) — если x < y, это y + (x – y) = x, иначе y. Для максимума: x – (diff & mask) — если x < y, это x – (x – y) = y, иначе x.

Но в функциях min_quick и max_quick есть шанс вызова undefined behavior при переполнении в x – y.

❯ Среднее арифметическое через биты

(x + y) >> 1;
((x ^ y) >> 1) + (x & y);

Два способа вычислить среднее целых чисел. Первый (x + y) >> 1 — это сложение и сдвиг вправо, что равно делению на два, но может вызвать переполнение при большом результате сложения. Второй ((x ^ y) >> 1) + (x & y) делает то же самое, но без риска переполнения. Он раскладывает сумму: (x ^ y) >> 1 — это полусумма различных битов, а x & y — общие биты. Их сложение даёт корректное среднее.

❯ Ответ — 42

#define SIX 1+5
#define NINE 8+1

int main() {
    int value = SIX * NINE;
    printf("Answer = %d\n", value);
    return 0;
}

Итак, изначально может показаться, что результатом будет 6*9=54. Но, как видно из заголовка, ответ будет 42, потому что препроцессор языка C трансформирует SIX * NINE в математическое выражение 1+5*8+1. Если в инструкциях #define использовать скобки, ответ будет более ожидаемым, то есть 54.

❯ Статические связанные списки

Код ниже выведет последовательность чисел от 1 до 4!

int main() {
    struct llist { int a; struct llist* next;};
    #define cons(x,y) (struct llist[]){{x,y}}
    struct llist *list=cons(1, cons(2, cons(3, cons(4, NULL))));
    struct llist *p = list;

    while(p != 0) {
        printf("%d\n", p->a);
        p = p->next;
    }
}

Структура llist содержит число a и указатель next на следующий элемент. Макрос cons создает анонимный массив структур. В строке создания списка происходит цепочка вызовов cons. Каждый cons создает элемент списка. Сначала создается последний элемент cons(4, NULL), затем он передается как аргумент в cons(3, ...), и так далее. В результате формируется односвязный список из четырёх элементов. Далее указатель p проходит по списку от начала до конца. На каждой итерации выводится значение a текущего элемента, затем p присваивается указатель на следующий элемент. Цикл завершается, когда p становится равным NULL.

Программа выведет числа 1, 2, 3, 4 каждое на новой строке. Однако код содержит проблему: макрос cons использует составные литералы, которые являются временными объектами. После завершения выражения они могут быть уничтожены, что делает указатели в списке недействительными. Это приводит к неопределенному поведению при попытке обхода списка.

❯ Генератор случайных чисел Лемера

Очень быстрый генератор псевдослучайных чисел. Подробнее можно почитать на странице википедии.

Алгоритм Lehmer64 — это быстрый генератор псевдослучайных чисел (ГПСЧ), основанный на мультипликативном линейном конгруэнтном методе. Он использует 128-битное состояние для генерации 64-битных случайных чисел, обеспечивая высокую производительность и достаточную статистическую случайность для большинства некриптографических задач.

Мультипликативный линейный конгруэнтный метод (мультипликативный конгруэнтный метод) — это алгоритм для генерации псевдослучайных чисел, основанный на линейной рекуррентной формуле. Простыми словами, метод создаёт последовательность чисел, где каждое последующее число зависит от предыдущего, но при этом существует цикл, повторяющийся бесконечное число раз (период).

Принцип работы
Основная формула метода: Xn+1 = (a ⋅ Xn + c) mod m, где:

• Xn+1 — следующее псевдослучайное число;

• Xn — текущее псевдослучайное число;

• a — мультипликативный множитель;

• c — приращение;

• m — модуль;

• X0 — начальное значение (seed).

И вот его простейшая реализация на C:

static __uint128_t g_lehmer64_state;

uint64_t lehmer64(void) {
    g_lehmer64_state *= 0xda942042e4dd58b5ULL;
    return g_lehmer64_state >> 64;
}

Каждый раз, когда нужно новое число, мы умножаем состояние на константу 0xda942042e4dd58b5ULL (высчитанная экспериментальным путем). g_lehmer64_state — это состояние размером 128 бит, на старте в котором хранится нечетный сид. После этого берем старшие 64 бита и возвращаем их, младшие остаются.

❯ 2 метода параллельного обращения битов в 32‑битном целочисленном

Первый метод использует 5 операций для обращения битов в 32‑битном слове. Каждая операция меняет местами соседние блоки битов, увеличивая размер блока на каждом шаге. Сначала меняются местами отдельные биты (нечетные с четными) с помощью маски 0x55555555. Затем меняются пары из двух битов с маской 0x33333333. Потом меняются группы по четыре бита (нибблы) с маской 0x0F0F0F0F. Далее меняются байты с маской 0x00FF00FF. В конце меняются местами два 16‑битных блока. Каждый шаг выполняется по схеме: сдвиг правой части влево, сдвиг левой части вправо, объединение через ИЛИ. После пяти таких шагов биты полностью развернуты.

uint32_t reverse_bits_static(uint32_t v) {
    v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
    v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
    v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
    v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
    v = (v >> 16) | (v << 16);
    return v;
}

Вторая функция работает в цикле и вычисляет маски динамически. Начинается с маски из всех единиц и размера блока, равного полной длине слова. На каждой итерации размер блока уменьшается вдвое. Маска обновляется операцией XOR: mask ^= (mask << s). Это создает маску с чередующимися блоками единиц и нулей нужной длины. Затем выполняется обмен битов между этими блоками. Цикл продолжается, пока размер блока больше нуля. Этот подход более универсален и не требует жестко заданных констант.

uint32_t reverse_bits_dynamic(uint32_t v) {
    unsigned int s = sizeof(v) * CHAR_BIT;
    unsigned int mask = ~0U;

    while ((s >>= 1) > 0) {
        mask ^= (mask << s);
        v = ((v >> s) & mask) | ((v << s) & ~mask);
    }
    return v;
}

Вообще, параллельное обращение битов применяется в сетевых протоколах, в криптографии, в драйверах. Метод выполняется за 5 фиксированных операций вместо цикла по 32 битам, что предсказуемо и быстро для real‑time систем.

❯ Параллельное вычисление четности числа

Этот код вычисляет битовую чётность 32‑битного числа. Алгоритм работает в два этапа. Сначала три операции сдвига и XOR сокращают 32 бита до 4 бит, сохраняя информацию о чётности. Затем используется табличный поиск: число 0x6996 содержит упакованную таблицу чётности для значений 0–15. Сдвиг на полученное 4‑битное значение и извлечение младшего бита даёт ответ. Очень быстро и невероятно бесполезно.

unsigned int parity(unsigned int v) {
    v ^= v >> 16;
    v ^= v >> 8;
    v ^= v >> 4;
    v &= 0xf;
    return (0x6996 >> v) & 1;
}

❯ Заключение

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

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

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

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