golang

Эффективная работа с битами при помощи Go

  • суббота, 1 июля 2023 г. в 00:00:31
https://habr.com/ru/companies/ruvds/articles/744230/

Это статья познакомит вас с использованием возможностей Go для выполнения манипуляций с битами. Здесь мы разберём установку, очистку, инвертирование, сдвиг битов, использование техники SWAR, эффективную обработку Юникода и прочие приёмы, позволяющие повысить продуктивность программирования.

На самом фундаментальном уровне программисту нужно манипулировать битами. Современные процессоры работают с данными через регистры, а не в виде отдельных битов, поэтому необходимо уметь управлять битами внутри регистра. Как правило, мы можем это делать в процессе программирования с использованием 8-, 16-, 32- и 64-битных целых чисел. Предположим, я хочу установить отдельный бит на 1. Выберем для этого бит по индексу 12 в 64-битном слове. Слово, где установлен только бит по индексу 12, выглядит как 1<<12: число 1, смещённое влево 12 раз, то есть 4096.

В Go форматирование числа производится с помощью функции fmt.Printf: мы используем строку с форматирующими инструкциями, сопровождая их значениями, которые хотим вывести. Форматирующая последовательность начинается с символа %, имеющего особое значение (для вывода % используется строка %%). Этот символ можно сопроводить буквой b, означающей «двоичный» (binary), буквой d (десятичный, decimal) или x (шестнадцатеричный, hexadecimal) формат. Иногда нам нужно указать минимальную длину вывода в символах, для чего мы предваряем такую букву числом. Например, fmt.Printf("%100d", 4096) выведет 100-символьную строку, оканчивающуюся на 4096 и начинающуюся пробелами. Вместо пробелов в качестве заполнения можно использовать нули, добавив соответствующий символ перед значением минимальной длины вывода (например, "%0100d"). В Go при помощи подобного приёма можно выводить отдельные биты так:

package main

import "fmt"

func main() {
    var x uint64 = 1 << 12
    fmt.Printf("%064b", x)
}

Выполнив эту программу, мы получим двоичную строку, представляющую 1<<12:

0000000000000000000000000000000000000000000000000001000000000000

Согласно общему правилу, при выводе чисел составляющие их цифры выводятся в порядке убывания своей значимости: например, мы пишем 1234, когда подразумеваем 1000 + 200 + 30 + 4. Аналогичным образом Go сначала выводит наиболее значимые биты, то есть число 1<<12 содержит 64-13=51 ведущий ноль, сопровождаемый 1 и 12 хвостовыми нулями.

Здесь будет интересно разобрать принцип представления в Go отрицательных чисел. Возьмём в качестве примера 64-битное значение -2. При использовании нотации дополнения до двух это число должно быть представлено как беззнаковое (1<<64)-2, то есть являться числом, все биты которого, кроме последнего, представлены единицами. Мы можем воспользоваться тем фактом, что операция приведения в Go (например, uint64(x)) сохраняет это двоичное представление:

package main

import "fmt"

func main() {
    var x int64 = -2
    fmt.Printf("%064b", uint64(x))
}

Выводом этой программы, как и ожидалось, будет: 

1111111111111111111111111111111111111111111111111111111111111110

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

  • & – побитовое И (AND)
  • | – побитовое ИЛИ (OR)
  • ^ – побитовое исключающее ИЛИ (XOR)
  • &^ – побитовое И-НЕТ (AND NOT)

Кроме того, символ ^ также можно задействовать для инвертирования всех битов слова, если использовать его в виде унарной операции: a ^ b вычисляет XOR для a и b в то время, как ^a инвертирует все биты a. Мы можем убедиться, что у нас получается a|b == (a^b) | (a&b) == (a^b) + (a&b).

Нам доступны и другие полезные тождественные равенства. Например, если даны два числа a и b, то a+b = (a^b) + 2*(a&b). В этом равенстве 2*(a&b) представляет перенос, а a^b сложение без переноса.

Рассмотрим пример: 0b1001 + 0b01001. Здесь 0b1 + 0b1 == 0b10, и это компонента 2*(a&b) при том, что 0b1000 + 0b01000 == 0b11000 выражается через a^b. Мы имеем 2*(a|b) = 2*(a&b) + 2*(a^b), а значит a+b = (a^b) + 2*(a&b) становится a+b = 2*(a|b) - (a^b). Эти связи являются действительными как в случае знаковых, так и в случае беззнаковых целых чисел, поскольку описываемые ими операции (побитовая логика, сложение и вычитание) на уровне битов идентичны.

▍ Установка, очистка и инвертирование битов


К этому моменту мы уже знаем, как создать 64-битное слово, где всего один бит установлен на 1 (например, 1<<12). При этом мы также можем, наоборот, создать слово, где все биты, кроме расположенного в позиции 12, будут равны нулю. Для этого мы выполним инвертирование всех битов имеющегося слова: ^uint64(1<<12). Перед инвертированием битов выражения иногда оказывается полезным указать его тип (взяв uint64 или uint32), чтобы результат получился однозначным. Затем эти слова можно использовать для воздействия на имеющееся слово:

  1. Чтобы установить 12-й бит слова w на единицу: w |= 1<<12.
  2. Чтобы очистить (установить на ноль) 12-й бит слова w: w &^= 1<<12 (что равнозначно w = w & ^uint64(1<<12)).
  3. Чтобы инвертировать только 12-й бит: w ^= 1<<12.

Также можно воздействовать на определённый диапазон битов. Например, нам известно, что в слове (1<<12)-1 все биты, за исключением 11 наименее значимых, нулевые.

  1. Чтобы установить 11 наименее значимых битов слова w на единицы: w |= (1<<12)-1.
  2. Чтобы очистить 11 наименее значимых битов слова w: w &^= (1<<12)-1.
  3. Чтобы инвертировать 11 наименее значимых битов: w ^= (1<<12)-1.

Выражение (1<<12)-1 является общим, то есть, если мы захотим воздействовать на 60 наименее значимых битов, то выполним (1<<60)-1. Оно сработает даже для 64 битов: (1<<64)-1 установит все биты на 1.

Также можно сгенерировать слово, в котором будет установлен произвольный диапазон битов: в слове ((1<<13)-1) ^ ((1<<2)-1) биты от индекса 2 до индекса 12 включительно установлены на 1, а остальные – на 0. Эта конструкция позволяет эффективно устанавливать, очищать или инвертировать произвольный диапазон битов в слове.

Хорошо, в слове мы можем установить любой желаемый бит, а как насчёт запроса по диапазону битов? Можно проверить, установлен ли 12-й бит в слове w, проверив, равно ли выражение w & (1<<12) нулю. Если 12-й бит в w установлен, оно будет иметь значение 1<<12. В противном случае его значение будет нулевым. Эту проверку можно расширить, а именно узнать, установлен ли какой-то из битов от индекса 2 до индекса 12 включительно на 1. Для этого нужно вычислить w & ((1<<13)-1) ^ ((1<<2)-1). Если ни один бит в указанном диапазоне не установлен на единицу, результатом будет ноль.

▍ Эффективные и безопасные операции с целыми числами


Представляя значения в битовом формате, мы можем писать более эффективный код или лучше понимать, как выглядит оптимизированный двоичный код. Рассмотрим в качестве примера проверку того, имеют ли два числа одинаковый знак: нам нужно будет узнать, больше они нуля, меньше или же равны ему. Первая наивная реализация может выглядеть так:

func SlowSameSign(x, y int64) bool {
return ((x < 0) && (y < 0)) || ((x >= 0) && (y >= 0))
}

Но давайте подумаем о том, что отличает отрицательные числа от других чисел: в них установлен последний бит. То есть их наиболее значимый бит в случае беззнакового значения равен единице. Если выполнить для двух целых чисел XOR, то в случае одинакового знака у этих чисел последний бит результата будет установлен на единицу. То есть результат оказывается положительным (или нулевым), только если знаки чисел совпадают. В таком случае будет предпочтительнее использовать для определения одинаковости знаков следующую функцию:

func SameSign(x, y int64) bool {
    return (x ^ y) >= 0
}

Предположим, что хотим проверить, отличаются ли x и y максимум на 1. Возможно, значение x меньше y, но оно может быть и больше.

Рассмотрим задачу вычисления среднего для двух чисел. У нас есть следующая корректная функция:

func Average(x, y uint16) uint16 {
    if y > x {
        return (y-x)/2 + x
    } else {
        return (x-y)/2 + y
    }
}

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

У нас есть ещё одно подходящее равенство x == 2*(x>>1) + (x&1). Оно означает, что x/2 находится в пределах [(x>>1), (x>>1)+1). То есть x>>1 является максимальным числом не больше x/2. И наоборот, (x+(x&1))>>1 является минимальным числом не меньше x/2.

Известно, что x+y = (x^y) + 2*(x&y). Тогда получается, что (x+y)>>1 == ((x^y)>>1) + (x&y) (игнорируя переполнения в x+y). Таким образом, ((x^y)>>1) + (x&y) является максимальным числом не больше (x+y)/2. Также известно, что x+y = 2*(x|y) - (x^y) или x+y + (x^y)&1= 2*(x|y) - (x^y) + (x^y)&1, а значит (x+y+(x^y)&1)>>1 == (x|y) - ((x^y)>>1) (игнорируя переполнения в x+y+(x^y)&1). Получается, что (x|y) - ((x^y)>>1) является минимальным числом не меньше (x+y)/2. Разница между (x|y) - ((x^y)>>1) и ((x^y)>>1) + (x&y) равна (x^y)&1. В итоге мы получаем две быстрых функции:

func FastAverage1(x, y uint16) uint16 {
    return (x|y) - ((x^y)>>1)
}
func FastAverage2(x, y uint16) uint16 {
    return ((x^y)>>1) + (x&y)
}

Несмотря на использование типа uint16, такой вариант работает независимо от размера числа (uint8, uint16, uint32, uint64), а также оказывается применим к знаковым числам (int8, int16, int32, int64).

▍ Эффективная обработка Юникода


В UTF-16 могут присутствовать суррогатные пары: первое слово в такой паре находится в диапазоне от 0xd800 до 0xdbff при том, что второе слово относится к диапазону от 0xdc00 до 0xdfff. Как можно эффективно обнаруживать суррогатные пары?

Если значения сохраняются с использованием типа uint16, тогда может показаться, что для выявления суррогатной пары потребуется два сравнения: (x>=0xd800) && (x<=0xdfff). Тем не менее эффективнее будет использовать тот факт, что операции вычитания естественным образом оборачиваются: 0-0xd800==0x2800. Таким образом, x-0xd800 будет находиться между 0 и 0xdfff-0xd800 включительно всякий раз, когда будет присутствовать значение, являющееся частью суррогатной пары. Однако любое другое значение будет больше 0xdfff-0xd800=0x7fff. Значит, требуется всего одно сравнение: (x-0xd800)<=0x7ff.

Определив наличие значения, которое может относиться к суррогатной паре, можно убедиться, что первое значение, x1, валидно (находится в диапазоне от 0xd800 до 0xdbff) с помощью условия (x-0xd800)<=0x3ff и проделать то же самое для второго значения, x2: (x-0xdc00)<=0x3ff. После этого можно будет перестроить кодовую точку как (1<<20) + ((x-0xd800)<<10) + x-0xdc00.

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

▍ Простая SWAR


В современных процессорах есть специализированные инструкции, способные работать над несколькими единицами данных. Этот метод называется SIMD (Single Instruction Multiple Data, ОКМД, одиночный поток команд, множественные потоки данных). Мы можем выполнять несколько операций, используя одну (или несколько) инструкций с помощью техники SWAR (SIMD within a register, ОКМД в регистре). Как правило, у нас есть 64-битное слово w (uint64) и мы хотим рассматривать его в виде вектора из восьми 8-битных слов (uint8).

Имея значение байта (uint8), я могу повторить его по всем байтам слова с помощью одного умножения: x * uint64(0x0101010101010101). Предположим, у нас есть 0x12 * uint64(0x0101010101010101) == 0x1212121212121212. Этот подход можно обобщить разными способами. Например, 0x7 * uint64(0x1101011101110101) == 0x7707077707770707.

Для удобства определим b80 с типом uint64 как равное 0x8080808080808080 и b01 с типом uint64 как равное 0x0101010101010101. Можно проверить, все ли байты меньше 128. Сначала мы повторим байтовое значение, в котором все биты, кроме самого значимого, установлены на ноль (0x80 * b01) или b80, а затем выполним (AND) с нашим 64-битным словом и проверим, равен ли результат нулю: (w & b80)) == 0.

Эта операция может скомпилироваться в две или три инструкции процессора.

Если предположить, что мы убедились в том, что все байты меньше 128, то можно выяснить, является ли любой из них нулевым, с помощью выражения ((w - b01) & b80) == 0. Если мы не уверены, что они меньше нуля, можно просто добавить операцию (((w - b01)|w) & b80) == 0. Проверка равенства байта нулю позволяет проверить, совпадают ли байтовые значения двух слов, w1 и w2, поскольку в таком случае w1^w2 будет иметь нулевое байтовое значение.

Также можно выстраивать более сложные операции, если предположить, что все байтовые значения не больше 128. К примеру, с помощью процедуры ((w + (0x80 - t) * b01) & b80) == 0 можно убедиться в том, что все байтовые значения меньше 7-битного значения (t). Если t является константой, тогда умножение будет вычислено при компиляции и окажется ненамного более затратным, чем проверка того, все ли байты меньше 128.

В Go мы проверяем, не превышает ли какое-то значение байта 77, предполагая, что все эти значения меньше 128, через проверку равенства b80 & (w+(128-77) * b01) нулю. Аналогичным образом можно проверить, все ли байтовые значения не меньше 7-битного t, предположив, что все они также меньше 128: ((b80 - w) + t * b01) & b80) == 0. Этот принцип можно обобщить и далее. Предположим, что хотим проверить, все ли байты не меньше 7-битного значения a и не больше 7-битного значения b. Для этого будет достаточно вычислить ((w + b80 - a * b01) ^ (w + b80 - b * b01)) & b80 == 0.

▍ Циклический сдвиг и реверсирование битов


Работая со словом, мы говорим, что сдвигаем биты, если смещаем их влево или вправо, также смещая оставшиеся биты в начале. Для более наглядной иллюстрации принципа предположим, что у нас есть 8-битное число 0b1111000, и мы хотим сдвинуть его влево на 3 бита. В Go для этого есть специальная функция bits.RotateLeft8 из пакета math/bits. Применив её, мы получим 0b10000111.

В Go отсутствует операция сдвига вправо. Тем не менее при обработке 8-битного числа сдвиг влево на 3 бита – это то же самое, что сдвиг вправо на 5 бит. Go предоставляет функции сдвига для 8-, 16-, 32- и 64-битных целых чисел.

Предположим, что хотим узнать, есть ли в двух 64-битных словах, w1 и w2, совпадающие байтовые значения, независимо от порядка их вхождения. Мы уже умеем эффективно проверять наличие совпадающих упорядоченных байтовых значений (например, (((w1^w2 - b01)|(w1^w2)) & b80) == 0). Чтобы сравнить все байты одного слова со всеми байтами другого, можно повторить ту же операцию столько раз, сколько в слове содержится байтов (для 64-битных чисел восемь раз), каждый раз сдвигая одно из слов на 8 бит:

(((w1^w2 - b01)|(w1^w2)) & b80) == 0
w1 = bits.RotateLeft64(w1,8)
(((w1^w2 - b01)|(w1^w2)) & b80) == 0
w1 = bits.RotateLeft64(w1,8)
...

Напомню, что слова можно интерпретировать как имеющие прямой порядок байтов или обратный, в зависимости от того, являются ли первые байты наименее значимыми или наиболее значимыми. Go позволяет разворачивать порядок байтов в 64-битном слове с помощью функции bits.ReverseBytes64 из пакета math/bits. В нём также есть аналогичные функции для 16- и 32-битных слов. Нам известно, что bits.ReverseBytes16(0xcc00) == 0x00cc. Реверсирование байтов в 16-битном слове и сдвиг на 8 бит являются равнозначными операциями.

Биты также можно реверсировать. Нам известно, что bits.Reverse16(0b1111001101010101) == 0b1010101011001111. В Go есть функции для реверсирования битов в 8-, 16, 32- и 64-битных словах. Во многих процессорах есть быстрые инструкции для реверсирования порядка битов, и эта операция может выполняться быстро.

▍ Быстрый подсчёт битов


Иногда оказывается полезным подсчитать, сколько битов в слове установлено на 1. В Go для этого есть быстрые функции из пакета math/bits, подходящие для слов из 8, 16, 32 и 64 бит. Таким образом, получается, что bits.OnesCount16(0b1111001101010101) == 10.

Аналогичным образом иногда нужно подсчитать количество хвостовых или ведущих нулей. Число хвостовых нулей – это число последовательных нулевых битов, находящихся в наименее значимых разрядах. К примеру, в слове 0b1 хвостового нуля нет, а вот в слове 0b100 их два. Когда входное значение является степенью двойки, количество хвостовых нулей равно логарифму по основанию два. Для вычисления числа хвостовых нулей можно использовать функции bits.TrailingZeros8, bits.TrailingZeros16 и так далее.

Количество ведущих нулей вычисляется аналогичным образом, но в этом случае мы начинаем с наиболее значимых разрядов. То есть 8-битное число 0b10000000 не имеет ведущих нулей, а в числе 0b00100000 их два. В этом случае нам помогают функции bits.LeadingZeros8, bits.LeadingZeros16 и так далее.

И хотя количество хвостовых нулей даёт непосредственно логарифм степеней двойки, количество ведущих нулей можно использовать для вычисления логарифма любого числа, округлённого до ближайшего целого значения. Для 32-битных чисел корректный результат даст такая функция:

func Log2Up(x uint32) int {
    return 31 - bits.LeadingZeros32(x|1)
}

Также можно вычислять и другие логарифмы. Чисто логически это должно быть возможно, так как, если log_b является логарифмом по основанию b, тогда log_b (x) = \log_2(x)/\log_2(b). Иными словами, все логарифмы находятся в пределах постоянного множителя (например, 1/log_2(b)).

Предположим, что нас интересует количество цифр, необходимых для представления целого числа (например, для 100 требуется три цифры). Общая формула будет выглядеть как ceil(log(x+1)), где логарифм должен вычисляться по основанию 10. Мы можем показать, что следующая функция (придуманная инженером по имени Кендалл Уиллетс) вычисляет нужное количество цифр для 32-битных чисел:

func DigitCount(x uint32) uint32 {
    var table = []uint64{
        4294967296, 8589934582, 8589934582,
        8589934582, 12884901788, 12884901788,
        12884901788, 17179868184, 17179868184,
        17179868184, 21474826480, 21474826480,
        21474826480, 21474826480, 25769703776,
        25769703776, 25769703776, 30063771072,
        30063771072, 30063771072, 34349738368,
        34349738368, 34349738368, 34349738368,
        38554705664, 38554705664, 38554705664,
        41949672960, 41949672960, 41949672960,
        42949672960, 42949672960}
    return uint32((uint64(x) + table[Log2Up(x)]) >> 32)
}

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

▍ Индексирование битов


При наличии слова иногда оказывается полезным вычислить позиции установленных битов. Представим, что в слове 0b11000111 мы хотим получить индексы 0, 1, 2, 6, 7, соответствующие 5 битам со значением 1. Эффективно определить, сколько индексов нужно произвести, нам позволяют функции bits.OnesCount.

Функции bits.TrailingZeros можно использовать для определения позиции бита. Также можно воспользоваться тем фактом, что x & (x-1) устанавливает на ноль наименее значимый бит в x. Следующая функция Go генерирует массив индексов:

func Indexes(x uint64) []int {
    var ind = make([]int, bits.OnesCount64(x))
    pos := 0
    for x != 0 {
        ind[pos] = bits.TrailingZeros64(x)
        x &= x - 1
        pos += 1
    }
    return ind
}

Получая на входе 0b11000111, она производит массив 0, 1, 2, 6, 7:

var x = uint64(0b11000111)
for _, v := range Indexes(x) {
    fmt.Println(v)
}

Если нам нужно вычислить биты в обратном порядке (7, 6, 2, 1, 0), это можно сделать с помощью функции реверсирования:

for _, v := range Indexes(bits.Reverse64(x)) {
    fmt.Println(63 - v)
}

▍ Заключение


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