Как убрать младший значащий бит из числа?
Установить, что старший и младший бит числа равны 1
Здравствуйте, нужно сгенерировать случайное 16 битное число и установить его старший и младший бит.
Бит 8, младший и старший бит (по книге)
Добрый день. Вот читаю книгу, и не пойму элементарной на первый взгляд вещи. Как понять.
Как получить младший байт и его старший бит
Подскажите как получить младший байт и его старший бит. И как сделать замену старшего бита младшего.
Как может число, младший бит которого установлен в единицу, делиться на два?
Хаюшки уважаемые программеры!В очередной раз столкнулся в книге с непоняткой.На этот раз логическое.
Решение
Результат вывода на консоли
1111100111111110000000011011101
1111100111000000000000000000000
Остались только старшие 8 единичных бит.
Добавлено через 1 минуту
Ни какой магии. Битовые операции. Вернее их эмуляция на C#.
Добавлено через 14 минут
При этом десятичное число может быть любым в диапазоне (0-65535)
Надо удалить ОДНУ единицу из бинарного представления? В Вашем ТЗ написано «в некоем числе не более восьми единичных разрядов. Если оказалось, что значащих единиц слишком много, удалить необходимое количество единиц, начиная с младшего разряда«. То есть по ТЗ надо оставить только 8 старших единиц в бинарном представлении.
То, что Вы пишите сейчас это совсем иное задание. В последнем посте, Вы фактически, пишите об удалении бита НЕЧЁТНОСТИ.
То есть между ТЗ в начале темы и в последнем посте очень БОЛЬШАЯ разница. Это два разных ТЗ и вряд ли здесь дело просто в описке.
Извиняюсь за неточность в ТЗ. Оно суть такое: есть некое число, допустим 32704. У него более 8 единичных битов(в двоичном представлении). Мы с помощью побитовых операций убираем последний(младший) единичный бит у числа. И получившееся мы и записываем в переменную, хранящую первое число. В нашем случае это 32640.
Было:
32704
111111111000000
Стало:
32640
111111110000000
Необходимо, чтобы все происходило в десятичном представлении.) В этом вся проблема.
Добавлено через 24 секунды
А Ваш код работает в двоичном, ну не совсем.
Добавлено через 3 минуты
То есть: на входе десятичное число. На выходе тоже.
Битовые операции
Данный урок посвящён битовым операциям (операциям с битами, битовой математике, bitmath), из него вы узнаете, как оперировать с битами – элементарными ячейками памяти микроконтроллера. Мы уже сталкивались с битовыми операциями в уроке про регистры микроконтроллера, сейчас рассмотрим всё максимально подробно. Данная тема является одной из самых сложных для понимания в рамках данного курса уроков, так что давайте разберёмся, зачем вообще нужно уметь работать с битами:
Данный урок основан на оригинальном уроке по битовым операциям от Arduino, можете почитать его здесь – там всё описано чуть более подробно.
Двоичная система и хранение данных
| 2 в степени | DEC | BIN |
| 0 | 1 | 0b00000001 |
| 1 | 2 | 0b00000010 |
| 2 | 4 | 0b00000100 |
| 3 | 8 | 0b00001000 |
| 4 | 16 | 0b00010000 |
| 5 | 32 | 0b00100000 |
| 6 | 64 | 0b01000000 |
| 7 | 128 | 0b10000000 |
Таким образом, степень двойки явно “указывает” на номер бита в байте, считая справа налево (примечание: в других архитектурах может быть иначе). Напомню, что абсолютно неважно, в какой системе исчисления вы работаете – микроконтроллеру всё равно и он во всём видит единицы и нули. Если “сложить” полный байт в десятичном представлении битов, то мы получим как раз 255: 128+64+32+16+8+4+2+1 = 255. Нетрудно догадаться, что число 0b11000000 равно 128+64, то есть 192. Именно таким образом и получается весь диапазон от 0 до 255, который умещается в один байт. Если взять два байта – будет всё то же самое, просто ячеек будет 16, то же самое для 4 байт – 32 ячейки с единицами и нулями, каждая имеет свой номер согласно степени двойки. Давайте начнём манипуляции с битами с самого простого – с макро-функций, которые идут “в комплекте” с ядром Arduino.
Макросы для манипуляций с битами
В “библиотеке” Arduino.h есть несколько удобных макросов, которые позволяют включать и выключать биты в байте:
| Макросы Arduino.h | Действие |
| bitRead(value, bit) | Читает бит под номером bit в числе value |
| bitSet(value, bit) | Включает (ставит 1) бит под номером bit в числе value |
| bitClear(value, bit) | Выключает (ставит 0) бит под номером bit в числе value |
| bitWrite(value, bit, bitvalue) | Ставит бит под номером bit в состояние bitvalue (0 или 1) в числе value |
| bit(bit) | Возвращает 2 в степени bit |
| Другие встроенные макросы | |
| _BV(bit) | Возвращает 2 в степени bit |
| bit_is_set(value, bit) | Проверка на включенность (1) бита bit в числе value |
| bit_is_clear(value, bit) | Проверка на выключенность (0) бита bit в числе value |
Битовые операции
Переходим к более сложным вещам. На самом деле они максимально просты для микроконтроллера, настолько просты, что выполняются за один такт. При частоте 16 МГц (большинство плат Arduino) одна операция занимает 0.0625 микросекунды.
Битовое И
И (AND), оно же “логическое умножение”, выполняется оператором & или and и возвращает следующее:
Основное применение операции И – битовая маска. Позволяет “взять” из байта только указанные биты:
То есть при помощи & мы взяли из байта 0b11001100 только биты 10000111, а именно – 0b11001100, и получили 0b10000100 Также можно использовать составной оператор &=
Битовое ИЛИ
ИЛИ (OR), оно же “логическое сложение”, выполняется оператором | или or и возвращает следующее:
Основное применение операции ИЛИ – установка бита в байте:
Также можно использовать составной оператор |=
Вы уже поняли, что указывать на нужные биты можно любым удобным способом: в бинарном виде (0b00000001 – нулевой бит), в десятичном виде (16 – четвёртый бит) или при помощи макросов bit() или _BV() ( bit(7) даёт 128 или 0b10000000, _BV(7) делает то же самое)
Битовое НЕ
Битовая операция НЕ (NOT) выполняется оператором
и просто инвертирует бит:
Также она может инвертировать байт:
Битовое исключающее ИЛИ
Битовая операция исключающее ИЛИ (XOR) выполняется оператором ^ или xor и делает следующее:
Данная операция обычно используется для инвертирования состояния отдельного бита:
То есть мы взяли бит №7 в байте 0b11001100 и перевернули его в 0, получилось 0b01001100, остальные биты не трогали.
Битовый сдвиг
Битовый сдвиг делает не что иное, как умножает или делит байт на 2 в степени. Да, это операция деления, выполняющаяся за один такт процессора! К этому мы ещё вернёмся ниже. Посмотрите на работу оператора сдвига и сравните её с макросами bit() и _BV() :
Включаем-выключаем
Вспомним пример из пункта про битовое ИЛИ, про установку нужного бита. Вот эти варианты кода делают одно и то же:
Как насчёт установки нескольких бит сразу?
Или прицельного выключения бит? Тут чуть по-другому, используя &= и
Выключить несколько бит сразу? Пожалуйста!
Именно такие конструкции встречаются в коде высокого уровня и библиотеках, именно так производится работа с регистрами микроконтроллера. Вернёмся к устройству Ардуиновских макросов:
Я думаю, комментарии излишни: макросы состоят из тех же элементарных битовых операций и сдвигов!
Быстрые вычисления
Как я уже говорил, битовые операции – самые быстрые. Если требуется максимальная скорость вычислений – их можно оптимизировать и подогнать под “степени двойки”, но иногда компилятор делает это сам, подробнее смотри в уроке про оптимизацию кода. Рассмотрим базовые операции:
Примечание: рассмотренные выше операции работают только с целочисленными типами данных!
Экономия памяти
При помощи битовых операций можно экономить немного памяти, пакуя данные в блоки. Например, переменная типа boolean занимает в памяти 8 бит, хотя принимает только 0 и 1. В один байт можно запаковать 8 логических переменных, например вот так:
Ещё интересный пример сжатия
Таким образом мы отбросили у красного и синего младшие (правые) биты, в этом и заключается сжатие. Чем больше битов отброшено – тем менее точно получится “разжать” число. Например сжимали число 0b10101010 (170 в десятичной) на три бита, при сжатии получили 0b10101000, т.е. потеряли три младших бита, и в десятичной уже получится 168. Для упаковки используется битовый сдвиг и маска, таким образом мы берём первые пять битов красного, шесть зелёного и пять синего, и задвигаем на нужные места в результирующей 16-битной переменной. Всё, цвет сжат и его можно хранить. Для распаковки используется обратная операция: выбираем при помощи маски нужные биты и сдвигаем их обратно в байт:
Как и в примере со светодиодами, мы просто брали нужные биты ( в этом случае младшие два, 0b11 ) и сдвигали их на нужное расстояние. Для распаковки делаем в обратном порядке:
И получим обратно наши байты. Также маску можно заменить на более удобную для работы запись, задвинув 0b11 на нужное расстояние:
Ну и теперь, проследив закономерность, можно сделать для себя функцию или макрос чтения пакета:
Где x это пакет, а y – порядковый номер запакованного значения. Выведем посмотрим:
“Трюки” с битами
На битовых операциях можно сделать очень много всего интересного, и работать оно будет очень быстро и занимать мало места. Огромный список битовых трюков и хаков можно посмотреть в этой статье, их там очень много и все с примерами. Есть ещё один небольшой сборник самых простых и полезных хаков вот здесь (английский). Его я перевёл, смотрите ниже под спойлером. Другой вариант перевода (могут быть не все трюки) можно посмотреть здесь.
Перемотка бита
Целые
Установка n го бита
Выключение n го бита
Инверсия n го бита
Округление до ближайшей степени двойки
Округление вниз
Получение максимального целого
Получение минимального целого
Получение максимального long
Умножение на 2
Деление на 2
Умножение на m ую степень двойки
Деление на m ую степень двойки
Остаток от деления
Проверка равенства
Проверка на чётность (кратность 2)
Обмен значениями
Получение абсолютного значения
Максимум из двух
Минимум из двух
Проверка на одинаковый знак
Смена знака
Вернёт 2 n
Является ли число степенью 2
Остаток от деления на 2 n на m
Среднее арифметическое
Получить m ый бит из n (от младшего к старшему)
Получить m ый бит из n (от старшего к младшему)
Проверить включен ли n ый бит
Выделение самого правого включенного бита
Выделение самого правого выключенного бита
Выделение правого включенного бита
Выделение правого выключенного бита
n + 1
n – 1
Получение отрицательного значения
if (x == a) x = b; if (x == b) x = a;
Поменять смежные биты
Different rightmost bit of numbers m & n
Common rightmost bit of numbers m & n
Десятичные дроби
Примечание: хаки с float могут не работать на Ардуино! Разбить float в массив бит (unsigned uint32_t)
Вернуть массив бит обратно в float
Быстрый обратный квадратный корень
Быстрый n ый корень из целого числа
Быстрая степень
Быстрый натуральный логарифм
Быстрая экспонента
Строки
Конвертировать в нижний регистр
Конвертировать в верхний регистр
Инвертировать регистр
Позиция буквы в алфавите (англ)
Позиция большой буквы в алфавите (англ)
Позиция строчной буквы в алфавите (англ)
Другое
Быстрая конвертация цвета R5G5B5 в R8G8B8
Приоритет операций
Чтобы не плодить скобки, нужно знать приоритет операций. В C++ он такой:
Как установить, сбросить, проверить нужный бит или битовые операции
Для тех кому надо освежить знания оставлю тут памятку, более подробно эти операции будут рассмотрены в статье.
Независимо от того какие микроконтроллеры Вы собираетесь программировать, первое что придётся освоить — это битовые операции.
Битовых операций в языке Си всего 6.
Начнем с того, что выводы микроконтроллера условно разделены на порты, у Atmega16 порт состоит из 8 выводов, у STM32f103 из 16 выводов.
Установить в 1 нулевой бит порта B можно следующим образом.
Таким образом, мы установили нулевой бит в 1, а все остальные в 0, то есть мы переопределили все биты порта. А что если мы хотим установить в 1 только нулевой бит и не задеть остальные? В таком случае нужно воспользоваться побитовым ИЛИ.
В результате мы изменили только нулевой бит порта.
Надо отметить, что в микроконтроллерах счёт начинается с нуля, то есть первый бит будет иметь нулевой порядковый номер, а порядковый номер восьмого бита будет 7.
Битовая операция НЕ — изменяет значение бита на противоположное.
Эта операция совместно с битовым НЕ может использоваться для сброса конкретного бита в ноль.
При такой записи, мы выставляем в единицу бит, который хотим обнулить, затем инвертируем получившееся число
В итоге мы выставили в 0 только первый бит.
Также эту операцию можно использовать для проверки чему равен бит. Например, нам надо проверить чему равен нулевой бит порта B, это можно сделать с помощью следующей конструкции.
Если бит равен единице, выражение в скобках будет правда, иначе — ложь.
Побитовое исключающее ИЛИ — если сумма соответствующих битов число чётное, результирующий бит 0, иначе 1.
С помощью этой операции можно инвертировать состояние выбранного бита. Например, к нулевому выводу порта подключен светодиод и при выполнении одного и того же фрагмента кода, мы хотим чтобы он погас если горит и наоборот, зажёгся если не горит.
Также с помощью этой операции можно определить равенство регистров. Например, мы хотим сравнить в одинаковом ли состоянии находятся порты B и D.
Если результат равен нулю, то содержимое регистров равно.
Логический сдвиг влево — все разряды при этом сдвигаются на одну позицию влево, самый левый бит теряется, а в самый правый бит записывается 0.
Операция логического сдвига влево эквивалентна умножению на 2.
0b0000 1011 = 11
0b0001 0110 = 22
Логический сдвиг вправо — все разряды при этом сдвигаются на одну позицию вправо, самый правый бит теряется, а в самый левый бит записывается 0.
Обстоятельно о подсчёте единичных битов
Я хотел бы подарить сообществу Хабра статью, в которой стараюсь дать достаточно полное описание подходов к алгоритмам подсчёта единичных битов в переменных размером от 8 до 64 битов. Эти алгоритмы относятся к разделу так называемой «битовой магии» или «битовой алхимии», которая завораживает своей красотой и неочевидностью многих программистов. Я хочу показать, что в основах этой алхимии нет ничего сложного, и вы даже сможете разработать собственные методы подсчёта единичных битов, познакомившись с фундаментальными приёмами, составляющими подобные алгоритмы.
Прежде чем мы начнём, я сразу хочу предупредить, что это статья не для новичков в программировании. Мне необходимо, чтобы читатель в общих чертах представлял себе простейшие битовые операции (побитовое «и», «или», сдвиг), хорошо владел шестнадцатеричной системой счисления и достаточно уверенно пользовался воображением, представляя в нём не всегда короткие битовые последовательности. По возможности, всё будет сопровождаться картинками, но сами понимаете, они лишь упрощают, но не заменяют полное представление.
Все описанные приёмы были реализованы на языке Си и протестированы в двух режимах: 32 и 64 бита. Таким образом, для более полного понимания статьи будет лучше, чтобы вы хотя бы приблизительно понимали язык Си. Тестирование проходило на процессоре Core 2 Duo E8400 @3GHz на 64-х битовой Windows 7. Измерение чистого времени работы программ проводилось с помощью утилиты runexe. Все исходные коды описываемых алгоритмов доступны в архиве на Яндекс диске, их компиляция проверена для компиляторов Visual C++, Intel C++, GCC и CLang, так что в принципе, проблем у вас быть не должно, если кто-то захочет перепроверить результаты у себя. Пользователи Linux, думаю, лучше меня знают, как им тестировать время работы программы у себя в системе, поэтому им советов не даю.
Среди читателей, возможно, будут такие, кому проще посмотреть всё то же самое на видео. Я записал такое видео (58 минут), в котором в формате презентации изложено в точности всё то же самое, что будет ниже по тексту, но может немного в другом стиле, более сухо и строго, тогда как текст я попытался немного оживить. Поэтому изучайте материал так, как кому удобнее.
Сейчас будут последовательно описаны алгоритмы, порождаемые тем или иным набором алхимических приёмов, в каждом разделе будет таблица сравнения времени работы для переменных разного размера, а в конце будет сводная таблица по всем алгоритмам. Во всех алгоритмах используются псевдонимы для чисел без знака от 8 до 64 бит.
Наивный подход
Очевидно, что битовая алхимия применяется вовсе не для того, чтобы блистать на собеседовании, а с целью существенного ускорения программ. Ускорения по отношению к чему? По отношению к тривиальным приёмам, которые могут прийти в голову, когда нет времени более детально вникнуть в задачу. Таковым приёмом и является наивный подход к подсчёту битов: мы просто «откусываем» от числа один бит за другим и суммируем их, повторяя процедуру до тех пор, пока число не станет равным нулю.
Я не вижу смысла что-либо комментировать в этом тривиальном цикле. Невооружённым взглядом ясно, что если старший бит числа n равен 1, то цикл вынужден будет пройтись по всем битам числа, прежде чем доберётся до старшего.
Меняя тип входного параметра u8 на u16, u32 и u64 мы получим 4 различные функции. Давайте протестируем каждую из них на потоке из 2 32 чисел, подаваемых в хаотичном порядке. Понятно, что для u8 у нас 256 различных входных данных, но для единообразия мы всё равно прогоняем 2 32 случайных чисел для всех этих и всех последующих функций, причём всегда в одном и том же порядке (за подробностями можно обратиться к коду учебной программы из архива).
Время в таблице ниже указано в секундах. Для тестирования программа запускалась трижды и выбиралось среднее время. Погрешность едва ли превышает 0,1 секунды. Первый столбец отражает режим компилятора (32-х битовый исходный код или 64-х битовый), далее 4 столбца отвечают за 4 варианта входных данных.
| Режим | u8 | u16 | u32 | u64 |
|---|---|---|---|---|
| x86 | 38,18 | 72,00 | 130,49 | 384,76 |
| x64 | 37,72 | 71,51 | 131,47 | 227,46 |
Как мы видим, скорость работы вполне закономерно возрастает с ростом размера входного параметра. Немного выбивается из общей закономерности вариант, когда числа имеют размер 64 бита, а подсчёт идёт режиме x86. Ясное дело, что процессор вынужден делать четырёхкратную работу при удвоении входного параметра и даже хорошо, что он справляется всего лишь втрое медленнее.
Первая польза этого подхода в том, что при его реализации трудно ошибиться, поэтому написанная таким образом программа может стать эталонной для проверки более сложных алгоритмов (именно так и было сделано в моём случае). Вторая польза в универсальности и относительно простой переносимости на числа любого размера.
Трюк с «откусыванием» младших единичных битов
Этот алхимический приём основан на идее обнуления младшего единичного бита. Имея число n, мы можем произнести заклинание n=n&(n-1), забирая у числа n его младшую единичку. Картинка ниже для n=232 прояснит ситуацию для людей, впервые узнавших об этом трюке.
Код программы не сильно изменился.
Теперь цикл выполнится ровно столько раз, сколько единиц в числе n. Это не избавляет от худшего случая, когда все биты в числе единичные, но значительно сокращает среднее число итераций. Сильно ли данный подход облегчит страдания процессора? На самом деле не очень, а для 8 бит будет даже хуже. Напомню, что сводная таблица результатов будет в конце, а здесь в каждом разделе будет своя таблица.
| Режим | u8 | u16 | u32 | u64 |
|---|---|---|---|---|
| x86 | 44,73 | 55,88 | 72,02 | 300,78 |
| x64 | 40,96 | 69,16 | 79,13 | 126,72 |
Предподсчёт
Не будем торопиться переходить к «жёстким» заклинаниям, рассмотрим последний простой приём, который может спасти даже самого неопытного мага. Данный вариант решения задачи не относится напрямую к битовой алхимии, однако для полноты картины должен быть рассмотрен в обязательном порядке. Заведём две таблицы на 256 и 65536 значений, в которых заранее посчитаны ответы для всех возможных 1-байтовых и 2-байтовых величин соответственно.
Теперь программа для 1 байта будет выглядеть так
Чтобы рассчитать число бит в более крупных по размеру числах, их нужно разбить на байты. Например, для u32 может быть вот такой код:
Или такой, если мы применяем таблицу предподсчёта для 2-х байт:
Ну а дальше вы догадались, для каждого варианта размера входного параметра n (кроме 8 бит) может существовать два варианта предподсчёта, в зависимости от того, которую из двух таблиц мы применяем. Думаю, читателю понятно, почему мы не можем просто так взять и завести таблицу BitsSetTableFFFFFFFF, однако вполне могут существовать задачи, где и это будет оправданным.
Быстро ли работает предподсчёт? Всё сильно зависит от размера, смотрите таблицы ниже. Первая для однобайтового предподсчёта, а вторая для двухбайтового.
| Режим | u8 | u16 | u32 | u64 |
|---|---|---|---|---|
| x86 | 0,01 | 1,83 | 21,07 | 36,25 |
| x64 | 0,01 | 1,44 | 24,79 | 26,84 |
Интересный момент: для режима x64 предподсчёт для u64 работает заметно быстрее, возможно, это особенности оптимизации, хотя подобное не проявляется во втором случае.
| Режим | u8 | u16 | u32 | u64 |
|---|---|---|---|---|
| x86 | — | 0,05 | 7,95 | 13,01 |
| x64 | — | 0,07 | 8,49 | 13,01 |
Важное замечание: данный алгоритм с использованием предподсчёта оказывается выгодным только лишь при соблюдении следующих двух условий: (1) у вас есть лишняя память, (2) вам требуется выполнять расчёт числа единичных битов намного больше раз, чем размер самой таблицы, то есть имеется возможность «отыграть» время, потраченное на предварительное заполнение таблицы каким-то из нехитрых алгоритмов. Пожалуй, можно также иметь в виду экзотическое условие, которое на практике всегда выполнено. Вы должны гарантировать, что обращение к памяти само по себе быстрое и не замедляет работу других функций системы. Дело в том, что обращение к таблице может выбросить из кэша то, что там было изначально и замедлить таким образом какой-то другой участок кода. Косяк это вы вряд ли найдёте быстро, однако подобные чудовищные оптимизации едва ли кому-то понадобятся на практике при реализации обычных программ.
Умножение и остаток от деления
Возьмем же наконец более сильные зелья с нашей алхимической полки. С помощью умножения и остатка от деления на степень двойки без единицы можно делать довольно интересные вещи. Начнём творить заклинание с одного байта. Для удобства обозначим все биты одного байта латинскими буквами от «a» до «h». Наше число n примет вид:
Теперь разобьём мысленно наши 24 бита на 8 блоков по 3 бита в каждом (см. нижеследующую картинку, первую строку таблички). Затем с помощью побитового «и» с маской 0x249249 (вторая строка таблички) обнулим в каждом блоке два старших бита.
Третья строка таблицы поясняет шестнадцатеричную запись маски. В последней строке показан результат, которого мы добивались: все биты исходного байта содержаться каждый в своём трёхбитовом блоке, но в ином порядке (порядок нам и не важен).
Теперь внимание: мы должны сложить эти 8 блоков – и получим сумму наших бит!
В случае когда n имеет размер 16 бит можно разбить его на две части по 8 бит. Например, так:
Дело в том, что нам необходимо, чтобы все биты исходного числа заняли правильные позиции в своих 4-битовых блоках (картинка выше), а коль скоро 8 и 4 не являются взаимно простыми числами, обычное копирование 8 битов 4 раза не даст правильного расположения нужных битов. Нам придётся добавить к нашему байту один нолик, то есть тиражировать 9 битов, так как 9 взаимно просто с 4. Так мы получим число, имеющее размер 36 бит, но в котором все биты исходного байта стоят на младших позициях 4-битовых блоков. Осталось только взять побитовое «и» с числом 0x111111111 (вторая строка на картинке выше), чтобы обнулить по три старших бита в каждом блоке. Затем блоки нужно сложить.
При таком подходе программа подсчёта единичных битов в байте будет предельно простой:
Недостаток программы очевиден: требуется выход в 64-битовую арифметику со всеми вытекающими отсюда последствиями. Можно заметить, что в действительности данная программа задействует только 33 бита из 64-х (старшие 3 бита обнуляются), и в принципе можно сообразить, как перенести данные вычисления в 32-х битовую арифметику, но рассказы о подобных оптимизациях не входят в тему этого руководства. Давайте пока просто изучать приёмы, а оптимизировать их вам придётся самим уже под конкретную задачу.
Ответим на вопрос о том, какого размера может быть переменная n, чтобы данный трюк правильно работал для неё. Коль скоро мы берём остаток от деления на 15, такая переменная не может иметь размер больше 14 бит, в противном случае придётся применить ветвление, как мы делали это раньше. Но для 14 бит приём работает, если добавить к 14-ти битам один нолик, чтобы все биты встали на свои позиции. Теперь я буду считать, что вы в целом усвоили суть приёма и сможете сами без труда подобрать множитель для тиражирования и маску для обнуления ненужных битов. Покажу сразу готовый результат.
Эта программа выше показывает, как мог бы выглядеть код, будь у вас переменная размером 14 бит без знака. Этот же код будет работать с переменной в 15 бит, но при условии, что максимум лишь 14 из них равные единице, либо если случай, когда n=0x7FFF мы разберём отдельно. Это всё нужно понимать для того, чтобы написать правильный код для переменной типа u16. Идея в том, чтобы сначала «откусить» младший бит, посчитать биты в оставшемся 15-ти битовом числе, а затем обратно прибавить «откушенный» бит.
Здесь точно также можно было вместо трех ветвлений взять 3 остатка от деления, но я выбрал ветвистый вариант, на моём процессоре он будет работать лучше.
Для n размером 64 бита мне не удалось придумать подходящего заклинания, в котором было бы не так много умножений и сложений. Получалось либо 6, либо 7, а это слишком много для такой задачи. Другой вариант — выход в 128-битовую арифметику, а это уже не пойми каким «откатом» для нас обернётся, неподготовленного мага может и к стенке отшвырнуть 🙂
Давайте лучше посмотрим на время работы.
| Режим | u8 | u16 | u32 | u64 |
|---|---|---|---|---|
| x86 | 39,78 | 60,48 | 146,78 | — |
| x64 | 6,78 | 12,28 | 31,12 | — |
Очевидным выводом из этой таблицы будет то, что 64-х битовая арифметика плохо воспринимается в 32-х битовом режиме исполнения, хотя в целом-то алгоритм неплох. Если вспомнить скорость алгоритма предподсчёта в режиме x64 для однобайтовой таблицы для случая u32 (24,79 с), то получим, что данный алгоритм отстаёт всего лишь на 25%, а это повод к соревнованию, воплощённому в следующем разделе.
Замена взятия остатка на умножение и сдвиг
Недостаток операции взятия остатка всем очевиден. Это деление, а деление – это долго. Разумеется, современные компиляторы знают алхимию и умеют заменять деление на умножение со сдвигом, а чтобы получить остаток, нужно вычесть из делимого частное, умноженное на делитель. Тем не менее, это всё равно долго! Оказывается, что в древних свитках заклинателей кода сохранился один интересный способ оптимизации предыдущего алгоритма. Мы можем суммировать k-битовые блоки не взятием остатка от деления, а ещё одним умножением на маску, с помощью которой обнуляли лишние биты в блоках. Вот как это выглядит для n размером в 1 байт.
Для начала снова тиражируем байт трижды и удаляем по два старших бита у каждого 3-битового блока с помощью уже пройденной выше формулы 0x010101⋅n & 0x249249.
Каждый трёхбитовый блок я для удобства обозначил заглавной латинской буквой. Теперь умножаем полученный результат на ту же самую маску 0x249249. Маска содержит единичный бит в каждой 3-й позиции, поэтому такое умножение эквивалентно сложению числа самого с собой 8 раз, каждый раз со сдвигом на 3 бита:
Что мы видим? Биты с 21 по 23 и дают нам нужную сумму! При этом переполнения в каком-либо из блоков справа невозможно, так как там ни в одном блоке не будет числа, большего 7. Проблема лишь в том, что если наша сумма равна 8, мы получим 0, но это не страшно, ведь этот единственный случай можно рассмотреть отдельно.
По сути, мы взяли код из предыдущего раздела и заменили в нём взятие остатка от деления на 7 на умножение, сдвиг и побитовое «И» в конце. При этом вместо 3-х ветвлений осталось лишь одно.
Чтобы составить аналогичную программу для 16 бит, нам нужно взять код из предыдущего раздела, в котором показано как это делается с помощью взятия остатка от деления на 15 и заменить данную процедуру умножением. При этом нетрудно заметить то, какие условия можно убрать из кода.
Для 32-х бит мы делаем то же самое: берём код из предыдущего раздела и, порисовав немного на бумаге, соображаем, каким будет сдвиг, если заменить остаток на умножение.
Для 64-х бит я тоже не смог придумать чего-то такого, чтобы не заставляло бы мой процессор выполнять роль печки.
| Режим | u8 | u16 | u32 | u64 |
|---|---|---|---|---|
| x86 | 12,66 | 42,37 | 99,90 | — |
| x64 | 3,54 | 4,51 | 18,35 | — |
Приятно удивили результаты для режима x64. Как и ожидалось, мы обогнали предподсчёт с однобайтовой таблицей для случая u32. Можно ли вообще обогнать предподсчёт? Хороший вопрос 🙂
Параллельное суммирование
Пожалуй, это самый распространённый трюк, который очень часто повторяют друг за другом не вполне опытные заклинатели, не понимая, как он точно работает.
Начнём с 1 байта. Байт состоит из 4-х полей по 2 бита, сначала просуммируем биты в этих полях, произнеся что-то вроде:
Вот пояснительная картинка к данной операции (по-прежнему, обозначаем биты одного байта первыми латинскими буквами):
Одно из побитовых «И» оставляет только младшие биты каждого двухбитового блока, второе оставляет старшие биты, но сдвигает их на позиции, соответствующие младшим битам. В результате суммирования получаем сумму смежных битов в каждом двухбитовом блоке (последняя строка на картинке выше).
Теперь сложим парами числа, находящиеся в двухбитовых полях, помещая результат в 2 четырёхбитовых поля:
Нижеследующая картинка поясняет результат. Привожу её теперь без лишних слов:
Наконец, сложим два числа в четырёхбитовых полях:
Действуя по аналогии, можно распространить приём на любое число бит, равное степени двойки. Число строк заклинания равно двоичному логарифму от числа бит. Уловив идею, взгляните вскользь на 4 функции, записанных ниже, чтобы убедиться в правильности своего понимания.
На этом параллельное суммирование не заканчивается. Развить идею позволяет то наблюдение, что в каждой строчке дважды используется одна и та же битовая маска, что как будто наводит на мысль «а нельзя ли как-нибудь только один раз выполнить побитовое «И»?». Можно, но не сразу. Вот что можно сделать, если взять в качестве примера код для u32 (смотрите комментарии).
В качестве упражнения я бы хотел предложить доказать самостоятельно то, почему нижеследующий код будет точным отображением предыдущего. Для первой строки я даю подсказку, но не смотрите в неё сразу:
Аналогичные варианты оптимизации возможны и для остальных типов данных.
Ниже приводятся две таблицы: одна для обычного параллельного суммирования, а вторая для оптимизированного.
| Режим | u8 | u16 | u32 | u64 |
|---|---|---|---|---|
| x86 | 7,52 | 14,10 | 21,12 | 62,70 |
| x64 | 8,06 | 11,89 | 21,30 | 22,59 |
| Режим | u8 | u16 | u32 | u64 |
|---|---|---|---|---|
| x86 | 7,18 | 11,89 | 18,86 | 65,00 |
| x64 | 8,09 | 10,27 | 19,20 | 19,20 |
В целом мы видим, что оптимизированный алгоритм работает хорошо, но проигрывает обычному в режиме x86 для u64.
Комбинированный метод
Мы видим, что наилучшие варианты подсчёта единичных битов – это параллельный метод (с оптимизацией) и метод тиражирования с умножением для подсчёта суммы блоков. Мы можем объединить оба метода, получая комбинированный алгоритм.
Первое, что нужно сделать — выполнить первые три строки параллельного алгоритма. Это даст нам точную сумму битов в каждом байте числа. Например, для u32 выполним следующее:
Теперь наше число n состоит из 4 байт, которые следует рассматривать как 4 числа, сумму которых мы ищем:
Мы можем найти сумму этих 4-х байт, если умножим число n на 0x01010101. Вы теперь хорошо понимаете, что означает такое умножение, для удобства определения позиции, в которой будет находиться ответ, привожу картинку:
Ответ находится в 3-байте (если считать их от 0). Таким образом, комбинированный приём для u32 будет выглядеть так:
Скорость работы этого метода вы можете посмотреть сразу в итоговой таблице.
Итоговое сравнение
Я предлагаю читателю самостоятельно сделать интересующие его выводы, изучив две нижеследующие таблицы. В них я обозначил название методов, программы к которым мы реализовали, а также пометил прямоугольной рамкой те подходы, которые я считаю наилучшими в каждом конкретном случае. Тех, кто думал, что предподсчёт всегда выигрывает, ожидает небольшой сюрприз для режима x64.
Итоговое сравнения для режима компиляции x86.
Итоговое сравнения для режима компиляции x64.
Замечание
Ни в коем случае не рассматривайте итоговую таблицу как доказательство в пользу того или иного подхода. Поверьте, что на вашем процессоре и с вашим компилятором некоторые числа в такой таблице будут совершенно иными. К сожалению, мы никогда не можем точно сказать, который из алгоритмов окажется лучше в том или ином случае. Под каждую задачу нужно затачивать конкретный метод, а универсального быстрого алгоритма, к сожалению, не существует.
Я изложил те идеи, о которых знаю сам, но это лишь идеи, конкретные реализации которых в разных комбинациях могут быть очень разными. Объединяя эти идеи разными способами, вы можете получать огромное количество разных алгоритмов подсчёта единичных битов, каждый из которых вполне может оказаться хорошим в каком-то своём случае.
Спасибо за внимание. До новых встреч!
UPD: Инструкция POPCNT из SSE4.2 не включена в список тестирования, потому что у меня нет процессора, который поддерживает SSE4.2.
