Биты и математика

Перед началом: базовый Go и циклы — модуль самодостаточен; отсылки к DP (модуль 16) и хеш-таблицам (модуль 4) по ходу текста. Инструменты: Go 1.27, math/bits, math/big. Трудоёмкость: ~4 ч (теория 1.5 ч · практика 2.5 ч).

🔥 Инцидент: «Шестьдесят четыре булевых поля и миграция на каждый флаг»

В сервисе доступа права пользователя хранились структурой из 64 полей bool: canRead, canWrite, canDeleteManyThings… На десяти миллионах записей это 640 МБ только под флаги, а каждое новое право требовало миграции и правки полусотни мест. Когда дисковое пространство начало кончаться, инженер предложил то, что надо было сделать сразу: одно поле uint64 и одна битовая маска. Память упала в 64 раза, новые права — без миграций, проверка — одна операция &.

В модуле — битовые операции и математика, которая встречается в каждом втором собеседовании: маски и подмножества, XOR-фокусы, НОД и решето Эратосфена, быстрое возведение в степень и аккуратность с переполнением int64.

📖 Теория

19.1 Двоичное представление и операции

Число в памяти — набор битов; операции над ними быстрые и часто решают задачу без данных:

Основы работы с битами — сдвиг и маска:

go
// Права: бит i — i-е право. Установить, проверить, снять.
const permWrite = 3
flags |= 1 << permWrite          // выдать
hasWrite := flags&(1<<permWrite) != 0 // проверить
flags &^= 1 << permWrite         // снять (AND NOT)

Идиома &^ («clear bits») в Go заслуживает отдельного внимания: это x & (^y), то есть «снять у x все биты, которые установлены в y».

19.2 Трюки, которые стоит знать

Три приёма наизусть и модуль math/bits впридачу:

go
x & (x - 1)   // снять самый младший единичный бит
x & (-x)      // оставить только самый младший единичный бит (lowbit)
x ^ y; y ^= x; x ^= y // swap двух целых без временной переменной

• x & (x-1) применяют в «числе единичных битов» и в проверке «степень двойки ли число»: x & (x-1) == 0 ⇔ у x ровно один бит.
• x & (-x) — основа структуры «дерево Фенвика», оно же младший бит множества.

Стандартная библиотека уже содержит быстрые версии:

go
bits.OnesCount64(x)  // число единиц (population count, одна инструкция CPU)
bits.LeadingZeros64(x) // старшие нули: как «нормализовать» диапазон
bits.Len64(x)        // минимальное число бит для x: floor(log2 x) + 1
bits.RotateLeft64(x, k) // циклический сдвиг: хеши, шифры, буферы

На собеседовании «посчитать единицы» от вас ждут цикл x &= x-1, а в проде — bits.OnesCount64: он компилируется в аппаратную инструкцию.

19.3 Маски, подмножества и XOR-приёмы

Перебор подмножеств. Все подмножества набора из n элементов — это все маски от 0 до 1<<n - 1; бит i означает «элемент i взят». Отсюда школьная задача становится циклом:

go
for mask := 0; mask < 1<<n; mask++ {
	sum := 0
	for i := 0; i < n; i++ {
		if mask&(1<<i) != 0 {
			sum += a[i]
		}
	}
	// sum — сумма подмножества mask
}

O(2ⁿ · n) — быстро на n ≤ 20 и смертельно после. Тот же приём лежит в основе DP по маскам (набор «кто уже выбран» — состояние DP): знаменитая задача коммивояжёра — это dp[mask][last], и она в нашем курсе сознательно оставлена за границей базы.

XOR-приёмы. Свойства x ^ x = 0 и x ^ 0 = x дают целую семью задач:

go
// single number: все числа, кроме одного, встречаются дважды.
single := 0
for _, v := range a {
	single ^= v // пары взаимно уничтожаются
}
// missing number в диапазоне [0, n]: XOR всех чисел и всех индексов.

19.4 НОД, НОК и простые числа

Алгоритм Евклида — НОД двух чисел за O(log min(a, b)):

go
func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b // рекурсию легко заменить циклом
	}
	return a
}

func lcm(a, b int) int { return a / gcd(a, b) * b } // деление раньше умножения

Порядок в lcm — не придирка: a * b может переполниться до деления. НОД массива — свёртка gcd слева направо; НОК — аналогично.

Простые числа. Проверка на простоту перебором — до √n (делитель больше корня невозможен: он оставил бы пару меньше корня). Для «всех простых до n» перебор не годится — нужно решето Эратосфена: помечаем кратные каждого найденного простого, начиная с его квадрата.

go
func sieve(n int) []bool {
	isPrime := make([]bool, n+1)
	for i := 2; i <= n; i++ {
		isPrime[i] = true
	}
	for p := 2; p*p <= n; p++ {
		if !isPrime[p] {
			continue
		}
		for m := p * p; m <= n; m += p { // начинать с p*p: меньшее уже помечено
			isPrime[m] = false
		}
	}
	return isPrime
}

Сложность — O(n log log n), память — n бит (часто []bool заменяют битовой маской: ещё в 8 раз компактнее — перекличка с §19.1).

19.5 Модульная арифметика и переполнение

При a·b mod m легко влететь в переполнение: 1<<62 * 3 уже не влезает в int64. Правил три:

1. Умножать после деления, где возможно: (a / gcd) * b.
2. Расширять разрядность: math/bits.Mul64 даёт 128-битное произведение (hi, lo), из которого % m берётся точно.
3. math/big для ценой читаемости и аллокаций — когда числа не влезают в 64 бита принципиально.

Быстрое возведение в степень — образец «разделяй пополам» из модуля 7:

go
func powMod(base, exp, mod uint64) (result uint64, mults int) {
	result = 1 % mod // 1 % 1 == 0: mod = 1 не ломает ответ
	base %= mod
	for exp > 0 {
		if exp&1 == 1 { // биты показателя решают, когда умножать
			result = result * base % mod
			mults++
		}
		base = base * base % mod // основа возводится в квадрат каждый шаг
		mults++
		exp >>= 1
	}
	return result, mults
}

Вместо O(exp) умножений — O(log exp), то есть 64 шага для степени до 2⁶⁴. Замечание про разрядность: result * base безопасно, пока mod заметно меньше 2³²; для модулей близких к 2⁶³ берут bits.Mul64 (128-битное произведение hi, lo) или math/big — иначе % mod посчитается от уже переполненного значения. Тот же приём — в RSA и в любом pow из криптографии. Обратный элемент по модулю (расширенный Евклид) и китайская теорема об остатках — следующий шаг, за границей базового курса.

19.6 Компромиссы

💻 Практика

1. Битовые хелперы. Реализуйте HasBit, SetBit, ClearBit, ToggleBit, CountBits (двумя способами: циклом x &= x-1 и bits.OnesCount64). Тесты: нули, все биты, границы 0 и 63.
2. Single number и missing number. Оба через XOR, O(1) памяти. Вторую задачу решите двумя способами (XOR и сумма 0..n минус сумма элементов) и объясните, какие данные ломают «решение через сумму».
3. Подмножества маской. Для набора из 10 чисел (фиксированный seed) найдите подмножество с максимальной суммой, не превосходящей target. Замерьте число итераций против наивного перебора «взять/не взять» — асимптотика одинаковая, цена разная.
4. Решето и память. Сравните sieve(10_000_000) с []bool и с битовой маской []uint64: посчитайте потребление памяти (в байтах) и время прогона. Объясните, где выгоднее битовая версия.
5. powMod с инвариантом. Реализуйте быстрое возведение в степень по модулю и проверьте инвариант «число умножений = 2·log₂(exp) + popcount» счётчиком. Тесты: exp = 0, mod = 1, base > mod, большой exp (2⁶⁰).

🧩 Quiz

✅ Итоги модуля

• Битовая маска заменяет пачку булевых полей: |, &, &^ — выдать, проверить, снять; память падает в 8–64 раза.
• Трюки x&(x-1), x&(-x) и пакет math/bits дают аппаратную скорость на типовых задачах про биты.
• XOR-свойства решают «парные/пропавшие» задачи без памяти; маски перебирают подмножества и лежат в основе DP по маскам.
• Математическая база: Евклид для НОД/НОК, перебор до √n для простых, решето для «всех до n», быстрое возведение в степень по модулю.
• Модульная арифметика требует дисциплины: деление до умножения, bits.Mul64 или math/big там, где 64 бит мало.

🔗 Мостик к Модулю 20

Все кирпичи базы на месте: структуры, сортировка, поиск, деревья, графы, DP, жадные, биты. Последний модуль курса — «Практикум: паттерны и план тренировок»: каталог «признак → паттерн → модуль», разбор трёх задач end-to-end, процесс решения из пяти шагов и восьминедельный план, по которому всё это закрепляется в навык.