TL; DR в статье приведены алгоритмы обработки коротких битовых строк, обычно вмещающихся в машинное слово, в большей степени эти алгоритмы предназначены для обработки строк длины 32 или 64, но многие из них можно применять для SIMD инструкций или даже GPU.
Суть в двух словах
В общем то большинство рассматриваемых алгоритмов основаны на двух идеях:
Для строк длины 8, а иногда даже 16 можно просто подсчитать результат операций.
Недавняя статья на Хабре в очередной раз показала неостывающий интерес к игре «Жизнь» в частности и всевозможным оптимизациям в общем. Статья и комментарии к ней, особенно любопытство к вычислениям на GPU, вдохновили меня на то, чтобы поделиться своими изысканиями на данном поприще и, забегая вперёд, скажу, что повествование пойдёт о расчётах на GPU, битовой магии, многопоточности и огромных полях для игры «Жизнь», порядка миллиарда клеток.
Сложно найти человека, не знакомого с игрой "Жизнь", придуманной английским математиком Джоном Конвеем еще в 1970 году, и до сих пор не теряющей своей популярности. Многие программисты писали свою реализацию этой игры, и еще одна вряд ли кого-то удивит. Однако эта игра является отличным примером, показывающим, насколько полезной может оказаться оптимизация вычислений, даже не меняющая асимтотическую сложность алгоритма. Мы начнем с простейшей реализации на c# и будем последовательно применять различные оптимизации, ускоряя работу программы.
Мы также улучшим алгоритм на Javascript, ускорив его в 10 раз по сравнению с наивной реализацией.
В конце статьи дана ссылка на код, а также на online-реализацию игры с оптимизированным алгоритмом на JavaScript, выполняющим до двухсот итераций в секунду на поле размера 1920x1080 (Full HD), где вы можете убить время поиграть в эту замечательную игру.
Читать полностью »
Существует классическая задача для собеседований, часто формулируемая следующим образом:
Имеется массив натуральных чисел. Каждое из чисел присутствует в массиве ровно два раза, и только одно из чисел не имеет пары. Необходимо предложить алгоритм, который за минимальное число проходов по массиву определяет число, не имеющее пары.
Полагаю, никто не обидится, если я тут же приведу и решение задачи: уникальный элемент будет совпадать с 
-суммой всех элементов массива, вычисляемой за линейное время.
Предлагаю поразмыслить над другой вариацией данной задачи. Что, если все элементы, кроме искомого, будут присутствовать в массиве не парами, а тройками? Насколько при этом усложнится решение и останется ли оно линейным?
Я хотел бы подарить сообществу Хабра статью, в которой стараюсь дать достаточно полное описание подходов к алгоритмам подсчёта единичных битов в переменных размером от 8 до 64 битов. Эти алгоритмы относятся к разделу так называемой «битовой магии» или «битовой алхимии», которая завораживает своей красотой и неочевидностью многих программистов. Я хочу показать, что в основах этой алхимии нет ничего сложного, и вы даже сможете разработать собственные методы подсчёта единичных битов, познакомившись с фундаментальными приёмами, составляющими подобные алгоритмы.
