Доброго времени суток, господа и дамы! Иногда у некоторых людей возникает желание заняться откровенным непотребством в программировании — то, что не несет практической пользы напрямую, но помогает развлечься. И я — не исключение. В этой статье я хочу рассказать вам о лайфхаках, трюках (магических и не очень) и алгоритмах на языке C!
Идея написать эту статью зародилась из моего поста, после него я начал серию статей, которая раскрывала много интересных моментов — от математических алгоритмов и оптимизации до ГПСЧ.
Если вы видите на экране эту часть нашей бесконечной саги о ненормальном программировании на C, значит, мы с вами прошли уже немало: от конвертации миль в километры через Фибоначчи до ГПСЧ и быстрых вычислений.
В этой статье будет еще порция интересных структур, алгоритмов, фишек.
❯ Содержание
Вы можете читать статьи в любом порядке, они независимы друг от друга:
«Математика, биты, магия и немного ненормального программирования на C»
«Фокусы, хаки, магия и прочее ненормальное программирование на C»
❯ Bit Interleaving (Morton code)
Согласно Википедии, код Мортона (называемый также Z-порядок, кривая Мортона, кривая Лебега) — это функция, которая отображает многомерные данные в одномерные. Идея — чередовать биты координатных значений.
Bit Interleaving (перемежение битов, интерливинг) — процесс изменения порядка следования битов в передаваемой последовательности. Цель — разнести ошибки так, чтобы они влияли на разбросанные биты, а не на последовательные.
static uint32_t split_bits(uint16_t x) { x = (x | (x << 8)) & 0x00FF00FF; x = (x | (x << 4)) & 0x0F0F0F0F; x = (x | (x << 2)) & 0x33333333; x = (x | (x << 1)) & 0x55555555; return x; } uint32_t morton_encode(uint16_t x, uint16_t y) { return split_bits(x) | (split_bits(y) << 1); } void morton_decode(uint32_t code, uint16_t *x, uint16_t *y) { uint32_t x_code = code & 0x55555555; uint32_t y_code = code & 0xAAAAAAAA; x_code = (x_code | (x_code >> 1)) & 0x33333333; x_code = (x_code | (x_code >> 2)) & 0x0F0F0F0F; x_code = (x_code | (x_code >> 4)) & 0x00FF00FF; x_code = (x_code | (x_code >> 8)) & 0x0000FFFF; y_code = (y_code | (y_code >> 1)) & 0x33333333; y_code = (y_code | (y_code >> 2)) & 0x0F0F0F0F; y_code = (y_code | (y_code >> 4)) & 0x00FF00FF; y_code = (y_code | (y_code >> 8)) & 0x0000FFFF; *x = (uint16_t)x_code; *y = (uint16_t)(y_code >> 1); }
Битовый интерливинг перемешивает биты двух чисел. Для координат x и y мы берем их бинарные представления и создаем новое число, куда поочередно записываем биты из x и y. К примеру, если x = 10 (1010) и y = 12 (1100), то процесс будет таким: возьмем младшие биты x (0) и y (0), соединив их, получаем 00. Затем следующий бит y (0) и следующий бит x (1), получаем 01. Затем бит y (1) и бит x (0), получаем 10. Наконец, старший бит y (1) и старший бит x (1), получаем 11. Итоговый код Мортона: 11 10 01 00 = 11100100₂ = 228.
Функция split_bits выполняет ключевую операцию — она раздвигает биты числа, вставляя между ними нули. Для 4-битного числа 1010 после split_bits получается 01000100 в бинарном виде.
Функция morton_encode вызывает функцию split_bits для x и y, после сдвигает результат для y на один бит влево и объединяет XOR’ом.
Функция morton_decode выполняет обратную операцию. Сначала она разделяет код на биты, принадлежащие x (нечетные позиции) и y (четные позиции), используя маски 0x55555555 и 0xAAAAAAAA. Затем сжимает биты обратно в 16-битные числа, выполняя операции, обратные split_bits.
Основное преимущество кода Мортона — сохранение пространственной локальности. Точки, близкие в двумерном пространстве, обычно имеют близкие значения кодов Мортона. Это свойство используется в пространственных индексах, квадродеревьях, компьютерной графике и GIS-системах для эффективной организации данных.
Давайте попробуем запустить и проверить алгоритм:
int main() { uint16_t x = 10; uint16_t y = 13; uint32_t code = morton_encode(x, y); printf("x=%u, y=%u\n", x, y); printf("Morton code: %u (0x%08X)\n", code, code); uint16_t decoded_x, decoded_y; morton_decode(code, &decoded_x, &decoded_y); printf("Decoded: x=%u, y=%u\n", decoded_x, decoded_y); return 0; }
При запуске получаем:
x=10, y=12 Morton code: 228 (0x000000E4) Decoded: x=10, y=6
Сам код Мортона благодаря тому, что упаковывает 2D/3D координаты в 1D число, используется в ГИС, базах данных, играх и прочих системах, где нужна упаковка координат.
❯ Код Грея
Код Грея, который носит также название зеркального, — это двоичный код, в котором две соседние кодовые комбинации различаются только цифрой в одном двоичном разряде. Иными словами, расстояние Хэмминга между соседними кодовыми комбинациями равно 1.
Зеркальным он называется из-за того, что первая половина значений при изменении порядка равна второй половине, за исключением старшего бита. Старший бит просто инвертируется. При делении каждой новой половины пополам это свойство сохраняется.
Пример кодов Грея порядка 2:
00
01
11
10
Его реализация на 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 позволяет этому алгоритму быть невероятно быстрым. Сам алгоритм используют в микроконтроллерах, энкодерах, системах обработки сигналов, адресации цилиндром дисков.
❯ Стандарты GNU
Бьюсь об заклад, что вы крайне редко видели код на GNU-стандартах. В качестве примера я хочу показать пример рабочей программы с устаревшими и специфичными вещами.
??=include <stdio.h> int $func(int array[static 10]) <% int sum = 0; for (int i = 9; i --> 0;) <% sum += array<:i:>; %> return sum; %> int $print_func(int array[static 10]) <% for (int i = 9; i >= 0; --i) <% printf("Value %i with index %i\n", array[i], i); %> return 0; %> int main() ??< int arr<:10:> = {[0]=1, [5]=5, [9]=9}; $print_func(arr); int result = (<% int temp = $func(arr); printf("Sum: %d??/n", temp); temp; %>); void *ptr = ??< &&label ??>; goto *ptr; label: return result; ??>
Скомпилировав код выше через gcc gnustd_fun.c -o gnustd_fun -std=gnu11 -trigraphs, мы получим:
Value 9 with index 9 Value 0 with index 8 Value 0 with index 7 Value 0 with index 6 Value 5 with index 5 Value 0 with index 4 Value 0 with index 3 Value 0 with index 2 Value 0 with index 1 Value 1 with index 0 Sum: 6
Этот код использует такие вещи, как триграфы ??= вместо символа #, ??< для открывающей фигурной скобки и ??> для закрывающей. Триграфы и диграфы (<% и %> также заменяют фигурные скобки, а <: и :> служат заменой квадратных скобок) были созданы для замены возможных несуществующих на клавиатуре символов скобок в стародавние времена.
Имена функций func и print_func начинаются с символа $ (php-разработчики должны пустить слезу), что является допустимым расширением компилятора.
Цикл в функции $func записан в необычной форме: for (int i = 9; i --> 0;). Оператор --> на самом деле комбинация постфиксного декремента i-- и оператора сравнения >. В функции main массив инициализируется следующим образом: {[0]=1, [5]=5, [9]=9}, где явно задаются значения только для конкретных индексов.
Далее используется составное выражение в круглых скобках ({ ... }), которое является расширением GCC и называется statement expression. Оно выполняет блок кода, а значением всего выражения становится результат последнего оператора внутри блока, в данном случае temp;. Это позволяет совместить вычисление суммы, её вывод через printf и передачу значения в переменную result.
Наиболее экзотическая часть кода — это использование указателей на метки. Конструкция &&label берет адрес метки в памяти, сохраняя его в указатель void *ptr. Затем с помощью оператора косвенного перехода goto *ptr; выполняется прыжок по этому адресу. Это нестандартное расширение GCC. После перехода на метку label: функция main возвращает ранее вычисленную сумму.
❯ Алгоритм Бойера–Мура
Алгоритм Бойера–Мура — алгоритм для поиска подстроки (образца) в строке. Разработан Робертом Бойером и Джеем Муром в 1977 году. Алгоритм использует предварительные вычисления над подстрокой, чтобы сравнение подстроки с исходной строкой осуществлялось не во всех позициях — часть проверок пропускается как заведомо не дающая результата.
Сам алгоритм работает достаточно просто: сравнивает символы подстроки справа налево, начиная с самого правого, один за другим с символами исходной строки. Если символы совпадают, производится сравнение предпоследнего символа подстроки и так до конца. Если все символы подстроки совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.
Ключевая идея: при несовпадении символов не продвигаться по тексту на один шаг, как в наивном методе, а перепрыгивать большие участки благодаря знанию структуры подстроки.
#define ALPHABET_SIZE 256 void preprocess_bad_char(char *pattern, int pattern_len, int bad_char[]) { for (int i = 0; i < ALPHABET_SIZE; i++) { bad_char[i] = pattern_len; } for (int i = 0; i < pattern_len - 1; i++) { bad_char[(unsigned char)pattern[i]] = pattern_len - 1 - i; } } int boyer_moore_search(char *text, char *pattern) { int text_len = strlen(text); int pattern_len = strlen(pattern); if (pattern_len == 0) { return 0; } int bad_char[ALPHABET_SIZE]; preprocess_bad_char(pattern, pattern_len, bad_char); int shift = 0; while (shift <= text_len - pattern_len) { int j = pattern_len - 1; while (j >= 0 && pattern[j] == text[shift + j]) { j--; } if (j < 0) { return shift; } int bad_char_shift = bad_char[(unsigned char)text[shift + j]] - (pattern_len - 1 - j); shift += bad_char_shift > 0 ? bad_char_shift : 1; } return -1; }
Сложность в худшем случае O(n*m), где n — длина текста, m — длина шаблона, но на практике часто достигается O(n/m) за счет больших сдвигов.
Код работает в три этапа: сначала создается таблица bad_char размером 256 (ASCII), где для каждого символа записывается расстояние от последнего вхождения в шаблоне до его конца. Для символов, отсутствующих в шаблоне, значение равно m.
Затем выполняется поиск: шаблон выравнивается с текстом, сравнение идет справа налево. При полном совпадении возвращается позиция. При несовпадении вычисляется сдвиг: из значения bad_char для символа текста, вызвавшего несовпадение, вычитается количество уже совпавших символов. Сдвиг всегда не менее 1.
Алгоритм использует две ключевые эвристики для ускорения поиска: правило плохого символа и правило хорошего суффикса. Эти эвристики позволяют алгоритму пропускать большие части строки при сравнении:
Правило плохого символа основано на том, что если в процессе сравнения подстроки с частью строки возникает несовпадение, алгоритм использует информацию о несовпадающем символе для того, чтобы пропустить несколько символов строки, а не проверять их снова.
Правило хорошего суффикса работает на основе совпадений в конце шаблона, называемых суффиксами. Когда происходит несовпадение, алгоритм использует информацию о совпадающих суффиксах для пропуска символов.
Давайте попробуем протестировать код:
int main() { char text[] = "ABAAABCDABCABCDABCDABDE"; char pattern[] = "ABCDABD"; int result = boyer_moore_search(text, pattern); if (result != -1) { printf("Pattern found at index: %d\n", result); } else { printf("Pattern not found\n"); } return 0; }
Будет следующий вывод: Pattern found at index: 15.
❯ Алгоритм Knuth–Morris–Pratt (KMP)
Алгоритм Кнута–Морриса–Пратта (KMP) — один из первых линейных алгоритмов поиска подстрок, разработанный Дональдом Кнутом, Джеймсом Моррисом и Воганом Праттом в 1977 году. Алгоритм стал революционным благодаря своей способности выполнять поиск за линейное время в худшем случае.
void computeLPSArray(char* pattern, int m, int* lps) { int len = 0; lps[0] = 0; int i = 1; while (i < m) { if (pattern[i] == pattern[len]) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } } void KMPSearch(char* pattern, char* text) { int m = strlen(pattern); int n = strlen(text); int* lps = (int*)malloc(m * sizeof(int)); computeLPSArray(pattern, m, lps); int i = 0; int j = 0; while (i < n) { if (pattern[j] == text[i]) { j++; i++; } if (j == m) { printf("Pattern found at index %d\n", i - j); j = lps[j - 1]; } else if (i < n && pattern[j] != text[i]) { if (j != 0) { j = lps[j - 1]; } else { i++; } } } free(lps); }
Алгоритм использует информацию о совпадающих префиксах и суффиксах для оптимизации процесса поиска. Ключевой компонент — префикс-функция (или таблица частичных совпадений). Она позволяет эффективно определять размер сдвига образца при несовпадении.
Временная сложность алгоритма KMP — O(n + m), где n — длина строки, m — длина подстроки.
Алгоритм работает в две фазы:
Сначала строится массив LPS (длины наибольшего суффикса, который является префиксом). Например, для "ABAB" такой суффикс-префикс — "AB" длиной 2. Функция
computeLPSArrayзаполняет этот массив, экономно переиспользуя уже вычисленные значения: при несовпадении символов длина откатывается к предыдущему подходящему префиксу.Затем идет поиск. Указатель i движется по тексту, j — по шаблону. При совпадении символов оба указателя идут вперед. При несовпадении ключевая оптимизация: j сдвигается не на начало шаблона, а на значение
lps[j-1]. Это позволяет пропустить заведомо неподходящие позиции, используя информацию о уже совпавшей части. Когда j достигает длины шаблона — найдено вхождение.
Главное: указатель по тексту никогда не движется назад, а умный сдвиг по шаблону через LPS даёт линейную сложность.
Давайте его также протестируем и запустим:
int main() { char text[] = "ABAAABCDABCABCDABCDABDE"; char pattern[] = "ABCDABD"; KMPSearch(pattern, text); return 0; }
И абсолютно такой же верный вывод: Pattern found at index 15.
У вас может появиться закономерный вопрос, а когда, как и почему можно использовать алгоритм KMP, а когда — Бойера–Мура? Вкратце, KMP более стабилен, но платит за это сравнением каждого символа и памятью O(m). Сильнее всего на данных с частыми частичными совпадениями, особенно на малых алфавитах (ДНК, бинарник). Указатель по тексту не откатывается.
Алгоритм Бойера–Мура в среднем быстрее. Прыгает по тексту, особенно на больших алфавитах.
❯ Type-punning через union
Для безопасного преобразования типов можно использовать union, что может быть иногда лучше, чем pointer casting.
Использование union для type-punning — это разрешённый в C способ безопасно интерпретировать одни и те же данные в памяти как другой тип. Он работает за счёт того, что члены union занимают общую область памяти.
Основное отличие от pointer casting в гарантиях. Прямое приведение указателей нарушает правило strict aliasing, что может привести к неопределённому поведению при оптимизациях компилятора. Union для этой цели стандартом C разрешён явно, что делает код корректным и переносимым.
Strict aliasing (строгий алиасинг) — это неофициальное название правила, согласно которому алиасинг запрещен для разнотипных объектов.
union float_int { float f; uint32_t i; }; uint32_t float_to_bits(float x) { union float_int u = {x}; return u.i; }
Пример с преобразованием float в uint32_t демонстрирует принцип: значение записывается в один член union, а читается через другой, что даёт доступ к побитовому представлению данных. Это простой и безопасный метод для низкоуровневых операций без копирования.
❯ Алгоритм Брезенхема для рисования линий
Алгоритм Брезенхэма — алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Он основан на наблюдении, что наклон линии между двумя точками можно выразить как отношение изменения координаты y к изменению координаты x.
void bresenham_line(int x0, int y0, int x1, int y1) { int dx = abs(x1 - x0); int dy = abs(y1 - y0); int sx = (x0 < x1) ? 1 : -1; int sy = (y0 < y1) ? 1 : -1; int err = dx - dy; while (1) { plot(x0, y0); // тут функция отрисовки точки if (x0 == x1 && y0 == y1) break; int e2 = err * 2; if (e2 > -dy) { err -= dy; x0 += sx; } if (e2 < dx) { err += dx; y0 += sy; } } }
Алгоритм Брезенхема рисует отрезок, выбирая следующие пиксели на основе целочисленной ошибки. Сначала вычисляются абсолютные приращения по осям и направления движения. Ключевая переменная ошибки инициализируется разностью этих приращений. В цикле ставится текущая точка. Если точка не конечная, вычисляется удвоенное значение ошибки. Проверка условия if (e2 > -dy) определяет, нужно ли изменить координату X. При истинности ошибка уменьшается на величину приращения по Y, а координата X сдвигается в своём направлении. Проверка условия if (e2 < dx) определяет, нужно ли изменить координату Y. При истинности ошибка увеличивается на приращение по X, а координата Y сдвигается. Оба условия могут выполниться за один шаг, что соответствует диагональному перемещению. Цикл продолжается до достижения конечных координат.
Весь процесс использует только сложение, вычитание и сравнение целых чисел, что собственно и дает высокую скорость растеризации отрезка.
Для полноты картины реализуем весь код:
#include <stdio.h> #include <stdlib.h> #define WIDTH 20 #define HEIGHT 20 char buffer[HEIGHT][WIDTH]; void clear_buffer() { for (int y = 0; y < HEIGHT; y++) { for (int x = 0; x < WIDTH; x++) { buffer[y][x] = ' '; } } } void plot(int x, int y) { if (x >= 0 && x < WIDTH && y >= 0 && y < HEIGHT) { buffer[y][x] = '*'; } } void bresenham_line(int x0, int y0, int x1, int y1) { int dx = abs(x1 - x0); int dy = abs(y1 - y0); int sx = (x0 < x1) ? 1 : -1; int sy = (y0 < y1) ? 1 : -1; int err = dx - dy; while (1) { plot(x0, y0); if (x0 == x1 && y0 == y1) break; int e2 = err * 2; if (e2 > -dy) { err -= dy; x0 += sx; } if (e2 < dx) { err += dx; y0 += sy; } } } void print_buffer() { for (int y = 0; y < HEIGHT; y++) { for (int x = 0; x < WIDTH; x++) { printf("%c", buffer[y][x]); } printf("\n"); } } int main() { clear_buffer(); bresenham_line(2, 3, 15, 10); bresenham_line(0, 19, 10, 5); print_buffer(); return 0; }
И при запуске дает вот такой вывод:
* ** ** * *** ** * ** * ** * * * * * * * * * * *
❯ Заключение
Спасибо за прочтение статьи! Я надеюсь, вы узнали что‑нибудь новенькое, или, может быть, какой‑нибудь трюк натолкнул вас на другой интересный алгоритм. Если нашли нюанс в самой статье — пишите в комментарии.
Если вам понравился изложенный материал, могу предложить вам подписаться на мой блог в телеграме. Если, конечно, вам статья понравилась и вы хотите видеть чуть больше.
Примеры работы кода вы можете увидеть в моем репозитории The Art Of Fun C.
❯ Источники
Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩
Перед оплатой в разделе «Бонусы и промокоды» в панели управления активируйте промокод и получите кэшбэк на баланс.
