Поговорим о побитовых операциях.

С ними привычно иметь дело embedded-разработчикам и тем, кто занимается криптографией. Также побитовые операции можно встретить в системном программировании, компьютерной графике и везде, где присутствует сильная ограниченность ресурсов или длительные вычисления.

В прикладном же программировании многие устанавливают (|) и проверяют параметры (&) через степени двойки. Как правило, дальше этого не заходит. Но всегда есть задачи, которые потребуют горизонтального масштабирования при высокой нагрузке в случае их решения явным или привычным способом. 

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

Побитовые операции: вспомним основы

Таблица истинности:

Побитовые операторы производят операции, используя двоичное представление числа. Среди наиболее частых случаев использования побитовых операций – такие:

Включение бита: y = x | (1 << n)

Предположим, у нас есть число 150 и для него необходимо установить третий бит:

    1001 0110 (150 – в двоичной системе счисления)
|   0000 1000 (1 << 3 – устанавливаем третий бит)
    ---------
    1001 1110 (158 – результат)

Очистка бита: y = x & ~(1 << n)

	1001 0111 (151 – в двоичной системе счисления)
|   1111 1011 (~(1 << 2) – выключаем второй бит)
    ---------
    1001 0011 (147 – результат)

Переключение бита: y = x ^ (1 << n)

	1101 1011 (219 – в двоичной системе счисления)
&  	0000 0100 (переключаем второй бит)
    ---------
    1101 1111 (223 – результат)

Обмен значений двух переменных: x = x ^ y ^ x

	0101 (x = 5)
^   0111 (y = 7)
    ----
    0010 (промежуточный результат)
^   0101 (x = 5)
    ----
    0111 (7 – итог) 

Или:

x ^= y

y ^= x

x ^= y

	0101 (x = 5)
^	0111 (y = 7)
	----
	0010 (x = 2)

	0111 (y = 7)
^  	0010 (x = 2)
	----
	0101 (y = 5)

	0010 (x = 2)
^	0101 (y = 5)
	----
    0111 (x = 7)

Также достаточно просто умножать и делить на степени двойки. Для этого достаточно сдвинуть число вправо или влево. Например, умножение числа 10 на 2: 10 << 1 = 20.

Для умножения на 4 сдвигаем уже на 2 бита. Например: 5 << 2 = 20

Аналогично производится деление чисел на 2, но сдвиг при этом производится вправо.

Применяем побитовые операции к задаче классификации 

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

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

Задача: приоритизировать данные на основе рейтинга (веса), полученного при объединении ключевых характеристик, с учётом важности каждой из них.

Рассмотрим эту задачу на примере моделей товара. Пусть набор множества неограниченного количества характеристик на входе даёт свёртку взвешенных сумм на выходе. Предположим, это будут пять ключевых характеристик: X₁, X₂, X₃, X₄, X₅. С точки зрения пользователя это информация о  цвете, материале, размере жесткого диска и т.д. Нормализованный вес характеристик определяется значениями от 0 до 10 – например, 7, 10, 5, 8, 9. При составлении рейтинга также имеет значение порядок данных характеристик.

Выделим по 4 бита на каждое значение, так как 10 в двоичном исчислении – 1010; соответственно, все числа меньше 10 также не выйдут за пределы четырёх битов. 

Объединим полученные данные в одно значение:

	var sum uint64 = 0
	ratingShift := 4
	weights := []uint64{9, 8, 5, 10, 7}
	for i := 0; i < len(weights); i++ {
		sum |= weights[i] << (i * ratingShift)
	}

То есть через операторы | и << мы каждое следующее число располагаем в следующих четырёх битах. При этом в более старших разрядах должны находиться значения с более высоким приоритетом. Располагаем числа справа налево – так, как это выглядит в памяти.

Данная комбинация даст нам десятичное число 501129. Если характеристика X₁ будет равна 10, то итоговый рейтинг станет равен 697737, что больше, чем предыдущее число. Нам это и нужно. 

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

Чтобы выделить значение характеристики, создаётся маска, позволяющая выделить необходимые четыре бита. Эта маска представляет собой число ...00001111 в двоичном исчислении. Сдвигая к правой границе нужную четвёрку чисел, все остальные позиции мы обнуляем, используя побитовое умножение (AND).

	mask := uint64((1 << 4) - 1)
	weight := (sum >> 16) & mask

Теперь модель имеет рейтинг, который хранится в одном месте; это позволяет легко и очень быстро выделять части рейтинга (веса) при необходимости. Если приоритизировать данные через циклы, то сложность алгоритма будет зависеть от количества характеристик. Внутри каждого вложенного цикла в свою очередь осуществляется сортировка для каждой подгруппы. Это сильно усложнит работу программы – как во временном отношении, так и в использовании памяти.  А в случае использования побитовых операций достаточно собрать такие весовые значения и отсортировать, что не будет по сложности превышать O(n²).

Стоило ли оно того? Например, мы могли с помощью ML получить какую-то одну вероятностную характеристику и пользоваться ей. Но всё-таки набор характеристик, хранящихся в одном месте, – лучше, чем одно весовое значение. Так мы получим преимущество пересчёта рейтинга на лету при изменении приоритета характеристик пользователем. Рассмотрим следующий пример.

Побитовые сдвиги для задачи рекомендации товаров из смежных категорий

Теперь в нашем примере у каждой модели есть значение рейтинга или вес. Предположим, пользователь добавил в избранное то, что ему понравилось. Дальше он может переопределить при необходимости порядок характеристик в соответствии со своими предпочтениями. В этом случае результирующее значение рейтинга будет пересчитано. Далее мы можем пересчитать рейтинг смежных категорий в соответствии с выбранным пользователем приоритетом характеристик и предложить ему те товары, которые близки или выше по рейтингу.

Рассмотрим на примере. Допустим, пользователь выбрал смартфон со следующим приоритетом характеристик по умолчанию: 

1. Объем жесткого диска (8). 

2. ОЗУ (7). 

3. Цвет (6) и т.д.

Данные характеристики представлены в виде вычисленного числового значения. Далее пользователь может переопределить их порядок, если посчитает более важным для себя “Цвет”, например. Или полностью опустить какую-то из характеристик. И затем происходит поиск моделей, которые находятся в том же каталоге. У них в свою очередь пересчитаются веса в соответствии с выбранным новым приоритетом. И в конце происходит их сортировка — с целью предложить пользователю что-то близкое.

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

Предположим для простоты, что вложенность категорий не больше четырёх. Соответственно, можно выделить 2¹⁶ = 65536 идентификаторов категорий для числа разрядности 64. Используем что-то вроде внутреннего идентификатора, а не идентификаторы из базы данных, во избежание переполнения накопителя. 

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

Например, для категории 401 полный путь вычисляется так:

	var categoryPath uint64 = 0
	shift := 16
	weights := []uint64{100, 201, 301, 401}
	for i := 0; i < len(weights); i++ {
		categoryPath |= weights[i] << (i * shift)
	}

Также вычисление можно представить в виде:

categoryPath := 100<<0 | 201<<16 | 301<<32 | 401<<48

Если пользователь выбрал одноместную палатку, то будем предлагать ему что-то аналогичное – тоже палатки: двухместные, трёхместные и далее по списку. 

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

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

Нам заранее известно, сколько слотов выделено для одной категории (16), поэтому для вычисления той или иной позиции достаточно хранить только количество сдвигов. В нашем случае достаточно хранить числа от 0 до 3, которым вполне хватит двух битов. 

Предположим, мы получили нужное значение. Для категории 401 оно будет равно числу 1. Таким образом, дальнейшие операции будут производиться со следующей позиции:

shift := 1
16 << shift = 32

Далее по общей части родительских категорий можно найти в базе данных смежные категории. Для этого создадим маску совпадения в данном случае первых двух родительских категорий:

mask := uint64((1 <<(16 << shift)) - 1)

Выполняем запрос для выборки категорий со следующим условием:

where category_path & mask = categoryPath & mask

Это даст нам список смежных категорий за одно обращение к хранилищу данных без последующего перебора и анализа связей.

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

Интересующие нас значения:

categories := value >> (16 << shift)

То есть обнуляем родительские категории, сдвигая число к правой границе на 32 бита. Оставшееся значение в свою очередь разбивается по 16 битов. И на выходе уже получаем значения идентификаторов 301, 302, 303, 401, то есть категорий, по которым будет произведён поиск моделей.

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

Сортировка и побитовые операции

Теперь у нас есть целочисленные значения рейтинга. Посмотрим на побитовые операции применительно к сортировке, в частности поразрядной (radix sort) O(k * n). Изначально данный алгоритм предназначен для сортировки целых чисел. Ориентируемся на него, так как в отличии от быстрой сортировки алгоритм имеет линейную сложность, стабилен и при большом количестве сортируемых данных - может дать выигрыш во временном отношении.

Попробуем приблизительно оценить встроенную сортировку (O(n²)), сортировку слиянием (merge sort) (O(n log n)) и поразрядную сортировку (radix sort) с побитовыми операциями. Опускаем при этом свою реализацию быстрой сортировки для целочисленных значений по двум причинам. Во-первых, сложность сортировки слиянием в худшем случае лучше. И выполняется быстрее на больших объемах сортируемых данных. Во-вторых, даже при каком-то улучшении для прикладной задачи не имеет большого смысла реализовывать быструю сортировку параллельно со встроенным вариантом.

Будем брать случайные числа от 0 до 2¹⁶.

const (
	RandLimit = 0x10000
)
func GenerateRandomArray(arrayLen int) []int {
	var a []int
	for i := 0; i < arrayLen; i++ {
		a = append(a, rand.Intn(RandLimit))
	}
	return a
}
func RadixSort(a []int) []int {
	size := len(a)
	var i, bit = 0, 0
	m := a[0]
	b := make([]int, size, size)
	for i = 0; i < size; i++ {
		if a[i] > m {
			m = a[i]
		}
	}
	for (m >> bit) > 0 {
		var bucket [2]int
		for i = 0; i < size; i++ {
			bucket[(a[i]>>bit)&1]++
		}
		bucket[1] += bucket[0]
		for i = size - 1; i >= 0; i-- {
			p := (a[i] >> bit) & 1
			b[bucket[p]-1] = a[i]
			bucket[p]--
		}
		for i = 0; i < size; i++ {
			a[i] = b[i]
		}
		bit++
	}
	return b
}

Генерируем 1000000 чисел и запускаем алгоритмы сортировки:

$ go run .
sort.Ints: 2.0456ms
radix sort: 958.6µs
merge sort: 1.0016ms

Результаты бенчмарк-тестирования:

$ go test -bench=. -benchtime 10s
pkg: sorting
BenchmarkSort-16                   	14100         850684 ns/op
BenchmarkMergeSort-16               5714          2155594 ns/op
BenchmarkRadixSort-16              	9589          1288526 ns/op
PASS
ok      sorting 55.880s

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

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

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

Посмотрим на производительность каждого из алгоритмов. Для этого загрузим данные из файла в количестве 10000 записей следующего вида:

1 8 7 5 10

9 3 7 5 10

9 4 6 4 3

И запустим алгоритмы:

const (
    featureQty = 5
    shiftSize  = 4
)

type key struct {
    weights []int
}
func readData(path string) [][]int {
    weights := [][]int{}
    inFile, err := os.Open(path)
    if err != nil {
        fmt.Println(err.Error() + :  + path)
        return nil
    }
    defer inFile.Close()
scanner := bufio.NewScanner(inFile)
for scanner.Scan() {
    str := strings.Split(scanner.Text(), " ")
    values := []int{}
    for _, s := range str {
        value, _ := strconv.Atoi(s)
        values = append(values, value)
    }
    weights = append(weights, values)
}
return weights

}
func rankUsingCycles(weights [][]int) [][]int {
    var sortKeys map[*key]int
    state := make([]*key, len(weights))
for k := 0; k < featureQty; k++ {
    if k == 0 {
        // sort for the first time
        sort.SliceStable(weights, func(i, j int) bool {
            return weights[i][k] > weights[j][k]
        })
    } else {
        for i := 0; i < len(weights); i++ {
            group := weights[i][0:k]
            for key, v := range sortKeys {
                if reflect.DeepEqual(group, key.weights) {
                    sort.SliceStable(weights[i:(i+v)], func(i, j int) bool {
                        return weights[i][k] > weights[j][k]
                    })
                    i += (v - 1)
                    break
                }
            }
        }
    }
    sortKeys = make(map[*key]int, len(weights))

    for i := 0; i < len(weights); i++ {
        if state[i] == nil {
            state[i] = &key{}
        }
        state[i].weights = append(state[i].weights, weights[i][k])
    }
    for _, key := range state {
        inserted := false
        for k := range sortKeys {
            if reflect.DeepEqual(k.weights, key.weights) {
                sortKeys[k]++
                inserted = true
                break
            }
        }
        if !inserted {
            sortKeys[key]++
        }
    }
}
return weights

}
func rankUsingBitwiseOperations(weights [][]int) []int {
    ratings := make([]int, 0, len(weights))
    for _, values := range weights {
        rate := 0
        for i := 0; i < len(values); i++ {
            rate |= values[i] << (i * shiftSize)
        }
        ratings = append(ratings, rate)
    }
    ratings = sort.IntSlice(ratings)
    return ratings
}

Результаты выполнения работы алгоритмов следующие:

Algorithm with cycles: 1.4650408s, μs (microseconds): 1465040
Algorithm with bitwise operations: 999.2µs, μs (microseconds): 999

Результаты тестирования показывают, что ранжирование данных при помощи циклов значительно уступает по производительности.

Побитовые операции – не только для низкоуровневого программирования

Побитовые операции можно использовать в прикладном программировании. Конечно, такой код требует особой аккуратности при разработке и поддержке и по большому счёту оправдан, когда это действительно нужно. Если его изолировать и не смешивать с основной бизнес-логикой, то не всё так страшно, как может показаться на первый взгляд. Выигрыш во временном отношении может быть при этом значительным – может более, чем на порядок превосходить обычные циклы. 

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

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

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

В итоге мы видим, что удалось значительно ускорить работу поставленной задачи. Классический алгоритм — хоть и сложно — но всё-таки можно незначительно улучшить. Производительность алгоритма в прикладной задаче можно улучшить более, чем на порядок. На нашем примере видно, что может быть и лучше 10².

Напоследок — список возможностей побитовых операций, которые могут пригодиться на практике:

• оптимизация распространённых операций: хранение опций в одной переменной, также определение чётности/нечётности, обмен значений переменных, приведение к верхнему/нижнему регистру и т. д.;

• более оптимальное использование памяти;

• использование в алгоритмизации – с целью оптимизации узких мест: замена дорогих операций умножения и деления и т. д.;

• возможность сохранения состояния какой-либо части системы в более компактном виде.

Полезные ссылки:

• Basics of Bit Manipulation

• Bit Twiddling Hacks - Stanford Computer Graphics Laboratory

• Bit Manipulation: Interview Questions and Practice Problems