Bit Manipulation

Побитовые операции: AND (&), OR (|), XOR (^), NOT (~), сдвиги (<<, >>). Эффективные решения через битовые трюки.

#1. Суть паттерна

Bit Manipulation — это техника решения задач на битовом уровне. Побитовые операции позволяют выполнять вычисления быстрее и компактнее, чем арифметические операции.

#Когда применять

✅ Уникальный элемент — XOR находит элемент, встречающийся один раз
✅ Проверка бита — установлен ли i-й бит
✅ Степень двойки — проверка n & (n-1) == 0
✅ Битовые маски — хранение множества в числе
✅ Арифметика без операторов — сумма через XOR и AND
✅ Манипуляции с битами — установка, сброс, инверсия бита

#Предусловия

Целочисленные данные — работа с int, не с float
Битовая природа задачи — чётность, степени двойки, подмножества
Оптимизация — когда нужно O(1) или очень быстрое решение

#Базовые операции

Операция	Обозначение	Пример	Результат
AND	&	5 & 3	1 (101 & 011 = 001)
OR	\|	5 \| 3	7 (101 \| 011 = 111)
XOR	^	5 ^ 3	6 (101 ^ 011 = 110)
NOT	~	~5	-6 (дополнение до 2)
Left Shift	<<	5 << 1	10 (101 << 1 = 1010)
Right Shift	>>	5 >> 1	2 (101 >> 1 = 10)

#Свойства XOR

a ^ a = 0      # XOR с собой = 0
a ^ 0 = a      # XOR с 0 = сам элемент
a ^ b = b ^ a  # Коммутативность
(a ^ b) ^ c = a ^ (b ^ c)  # Ассоциативность

#Основные трюки

# Проверка на степень двойки
n > 0 and (n & (n - 1)) == 0

# Убрать младший 1
n & (n - 1)

# Получить младший 1
n & -n

# Проверить чётность
n & 1 == 0

# Умножить на 2
n << 1

# Разделить на 2
n >> 1

# Проверить бит i
(n >> i) & 1

# Установить бит i
n | (1 << i)

# Сбросить бит i
n & ~(1 << i)

# Инвертировать бит i
n ^ (1 << i)

#3. Разбор задач

#Задача 1: Single Number (LeetCode 136) 🟩 Easy

Ссылка: https://leetcode.com/problems/single-number/

Условие: Дан непустой массив целых чисел nums, где каждый элемент встречается дважды, кроме одного. Найдите этот уникальный элемент.

Примеры:

Ввод: nums = [2,2,1]
Вывод: 1

Ввод: nums = [4,1,2,1,2]
Вывод: 4

Ввод: nums = [1]
Вывод: 1

Ограничения:

1 <= nums.length <= 3 × 10⁴
-3 × 10⁴ <= nums[i] <= 3 × 10⁴
Только один элемент встречается один раз, остальные — дважды

💡 Подсказка: Используйте свойство XOR: a ^ a = 0, a ^ 0 = a. XOR всех элементов сократит пары.

#Визуализация

nums = [4, 1, 2, 1, 2]

XOR всех элементов:
4 ^ 1 ^ 2 ^ 1 ^ 2

Группируем:
4 ^ (1 ^ 1) ^ (2 ^ 2)
4 ^ 0 ^ 0
4

Пары сократились, остался уникальный элемент!

Решение:

def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

Объяснение:

XOR коммутативен и ассоциативен
a ^ a = 0 (пары сокращаются)
a ^ 0 = a (остаётся уникальный элемент)

Сложность:

Время: O(n)
Память: O(1)

#Задача 2: Number of 1 Bits (LeetCode 191) 🟩 Easy

Ссылка: https://leetcode.com/problems/number-of-1-bits/

Условие: Напишите функцию, которая принимает беззнаковое целое число и возвращает количество единичных битов в его двоичном представлении (вес Хэмминга).

Примеры:

Ввод: n = 00000000000000000000000000001011 (11)
Вывод: 3

Ввод: n = 00000000000000000000000010000000 (128)
Вывод: 1

Ввод: n = 11111111111111111111111111111101
Вывод: 31

Ограничения:

Вход — бинарная строка длины 32

💡 Подсказка: Используйте трюк n &= n - 1, который убирает младший бит 1.

Решение:

def hammingWeight(n):
    count = 0
    while n:
        n &= n - 1  # Убирает младший 1
        count += 1
    return count

Объяснение:

n &= n - 1 убирает младший бит 1
Например: 1010 & 1001 = 1000
Каждый цикл убирает один бит 1

Сложность:

Время: O(number of 1 bits) = O(1) для 32 бит
Память: O(1)

#Задача 3: Counting Bits (LeetCode 338) 🟦 Easy

Ссылка: https://leetcode.com/problems/counting-bits/

Условие: Дано целое число n. Верните массив длины n + 1, где array[i] — количество единичных битов в числе i.

Примеры:

Ввод: n = 2
Вывод: [0,1,1]
Объяснение: 0→0, 1→1, 2→10

Ввод: n = 5
Вывод: [0,1,1,2,1,2]
Объяснение: 0→0, 1→1, 2→10, 3→11, 4→100, 5→101

Ограничения:

0 <= n <= 10⁵

💡 Подсказка: dp[i] = dp[i >> 1] + (i & 1). Биты(i) = биты(i/2) + младший бит.

Решение:

def countBits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

Объяснение:

i >> 1 = i / 2 (отбрасывает младший бит)
i & 1 = 1 если i нечётное, 0 иначе
Биты(i) = Биты(i/2) + младший бит

Сложность:

Время: O(n)
Память: O(n)

#Задача 4: Reverse Bits (LeetCode 190) 🟦 Easy

Ссылка: https://leetcode.com/problems/reverse-bits/

Условие: Разверните биты беззнакового 32-битного целого числа.

Примеры:

Ввод: n = 00000010100101000001111010011100
Вывод: 964176192 (00111001011110000010100101000000)

Ввод: n = 11111111111111111111111111111101
Вывод: 3221225471 (10111111111111111111111111111111)

Ограничения:

n — 32-битное беззнаковое целое

💡 Подсказка: Для каждого из 32 бит: сдвиньте результат влево, добавьте младший бит n, сдвиньте n вправо.

Решение:

def reverseBits(n):
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

Объяснение:

result << 1 — сдвигаем результат влево
n & 1 — берём младший бит n
| — добавляем бит к результату
n >>= 1 — сдвигаем n вправо

Сложность:

Время: O(32) = O(1)
Память: O(1)

#Задача 5: Missing Number (LeetCode 268) 🟦 Easy

Ссылка: https://leetcode.com/problems/missing-number/

Условие: Дан массив nums из n различных чисел в диапазоне [0, n]. Найдите единственное пропущенное число.

Примеры:

Ввод: nums = [3,0,1]
Вывод: 2

Ввод: nums = [0,1]
Вывод: 2

Ввод: nums = [9,6,4,2,3,5,7,0,1]
Вывод: 8

Ограничения:

n == nums.length
1 <= n <= 10⁴
0 <= nums[i] <= n

💡 Подсказка: XOR всех индексов и значений. Пары сократятся, останется пропущенное число.

Решение:

def missingNumber(nums):
    n = len(nums)
    result = n  # Включаем n
    for i in range(n):
        result ^= i ^ nums[i]
    return result

Объяснение:

result = n (длина массива, тоже часть диапазона)
XOR с i и nums[i] для всех i
Все числа 0..n-1 XOR с их индексами сократятся
Останется пропущенное число

Сложность:

Время: O(n)
Память: O(1)

#Задача 6: Sum of Two Integers (LeetCode 371) 🟦 Medium

Ссылка: https://leetcode.com/problems/sum-of-two-integers/

Условие: Даны два целых числа a и b. Верните их сумму без использования операторов + и -.

Примеры:

Ввод: a = 1, b = 2
Вывод: 3

Ввод: a = 2, b = 3
Вывод: 5

Ограничения:

-1000 <= a, b <= 1000

💡 Подсказка: a ^ b — сумма без переноса. (a & b) << 1 — перенос. Повторяйте, пока перенос не станет 0.

Решение:

def getSum(a, b):
    # Для Python с отрицательными числами
    MASK = 0xFFFFFFFF
    MAX_INT = 0x7FFFFFFF

    while b != 0:
        carry = (a & b) << 1
        a = (a ^ b) & MASK
        b = carry & MASK

    return a if a <= MAX_INT else ~(a ^ MASK)

Объяснение:

a ^ b — сумма без переноса
(a & b) << 1 — перенос
Цикл: a = сумма, b = перенос, пока b != 0
MASK для обработки отрицательных чисел в Python

Сложность:

Время: O(1) — максимум 32 итерации
Память: O(1)

#Задача 7: Bitwise AND of Numbers Range (LeetCode 201) 🟦 Medium

Ссылка: https://leetcode.com/problems/bitwise-and-of-numbers-range/

Условие: Даны два целых числа left и right. Верните bitwise AND всех чисел в диапазоне [left, right] включительно.

Примеры:

Ввод: left = 5, right = 7
Вывод: 4
Объяснение: 5 & 6 & 7 = 101 & 110 & 111 = 100 = 4

Ввод: left = 0, right = 0
Вывод: 0

Ввод: left = 1, right = 2147483647
Вывод: 0

Ограничения:

0 <= left <= right <= 2³¹ - 1

💡 Подсказка: AND всех чисел в диапазоне = общий префикс битов left и right. Сдвигайте, пока не совпадут.

Решение:

def rangeBitwiseAnd(left, right):
    shift = 0
    # Находим общий префикс
    while left < right:
        left >>= 1
        right >>= 1
        shift += 1
    return left << shift

Объяснение:

Сдвигаем left и right, пока они не совпадут
Это находит общий префикс битов
Сдвигаем результат обратно
Биты, differing в диапазоне, станут 0

Сложность:

Время: O(log right) = O(32) = O(1)
Память: O(1)

#Задача 8: Find the Difference (LeetCode 389) 🟦 Easy

Ссылка: https://leetcode.com/problems/find-the-difference/

Условие: Даны две строки s и t. Строка t получена перемешиванием s с добавлением одной буквы. Найдите добавленную букву.

Примеры:

Ввод: s = "abcd", t = "abcde"
Вывод: "e"

Ввод: s = "", t = "y"
Вывод: "y"

Ограничения:

0 <= s.length <= 1000
t.length == s.length + 1
s и t из строчных английских букв

💡 Подсказка: XOR всех символов s + t. Пары сократятся, останется добавленный символ.

Решение:

def findTheDifference(s, t):
    result = 0
    for c in s + t:
        result ^= ord(c)
    return chr(result)

Объяснение:

XOR всех символов s и t
Каждый символ из s встречается дважды (в s и в t)
Добавленный символ встречается один раз
ord() — код символа, chr() — обратно

Сложность:

Время: O(n)
Память: O(1)

#Задача 9: Power of Two (LeetCode 231) 🟦 Easy

Ссылка: https://leetcode.com/problems/power-of-two/

Условие: Дано целое число n. Верните true, если оно является степенью двойки.

Примеры:

Ввод: n = 1
Вывод: true (2⁰ = 1)

Ввод: n = 16
Вывод: true (2⁴ = 16)

Ввод: n = 3
Вывод: false

Ввод: n = 4
Вывод: true (2² = 4)

Ограничения:

-2³¹ <= n <= 2³¹ - 1

💡 Подсказка: Степени двойки имеют ровно один бит 1. Проверьте: n > 0 and (n & (n - 1)) == 0.

#Визуализация

n = 8 (1000 в двоичной)
n - 1 = 7 (0111 в двоичной)

n & (n-1):
  1000  (8)
& 0111  (7)
------
  0000  (0) ← степень двойки!

n = 6 (110 в двоичной)
n - 1 = 5 (101 в двоичной)

n & (n-1):
  110  (6)
& 101  (5)
-----
  100  (4) ← не 0, не степень двойки!

Решение:

def isPowerOfTwo(n):
    return n > 0 and (n & (n - 1)) == 0

Объяснение:

n > 0 — отрицательные числа не степени двойки
n & (n - 1) убирает младший бит 1
Если результат 0 — был ровно один бит 1

Сложность:

Время: O(1)
Память: O(1)

#Задача 10: Maximum XOR of Two Numbers (LeetCode 421) 🟦 Medium

Ссылка: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/

Условие: Дан целочисленный массив nums. Верните максимальный результат nums[i] XOR nums[j], где 0 <= i <= j < n.

Примеры:

Ввод: nums = [3,10,5,25,2,8]
Вывод: 28
Объяснение: 5 XOR 25 = 28

Ввод: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Вывод: 127

Ограничения:

1 <= nums.length <= 2 × 10⁵
0 <= nums[i] <= 2³¹ - 1

💡 Подсказка: Для каждого бита от старшего к младшему: пытаемся получить 1 в результате. Проверяем, есть ли пара с нужным префиксом.

Решение:

def findMaximumXOR(nums):
    result = 0
    for bit in range(31, -1, -1):
        result <<= 1
        # Префиксы чисел с текущим битом
        prefixes = {num >> bit for num in nums}
        # Пытаемся получить 1 в текущем бите
        result += any(result ^ 1 ^ p in prefixes for p in prefixes)
    return result

Объяснение:

Идём от старшего бита к младшему
result <<= 1 — сдвигаем текущий результат
prefixes — множество префиксов чисел
result ^ 1 ^ p — желаемый префикс для получения 1
any() — существует ли такая пара

Сложность:

Время: O(32 × n) = O(n)
Память: O(n)

#Задача 11: Binary Watch (LeetCode 401) 🟦 Easy

Ссылка: https://leetcode.com/problems/binary-watch/

Условие: Бинарные часы имеют 4 светодиода для часов (0-11) и 6 для минут (0-59).

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

Примеры:

Ввод: turnedOn = 1
Вывод: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

Ввод: turnedOn = 9
Вывод: []

Ограничения:

0 <= turnedOn <= 10

💡 Подсказка: Переберите все часы (0-11) и минуты (0-59). Проверьте, что количество бит 1 равно turnedOn.

Решение:

def readBinaryWatch(turnedOn):
    result = []
    for h in range(12):
        for m in range(60):
            if bin(h).count('1') + bin(m).count('1') == turnedOn:
                result.append(f"{h}:{m:02d}")
    return result

Объяснение:

Перебираем все возможные времена (12 × 60 = 720)
bin(h).count('1') — количество бит 1 в часах
bin(m).count('1') — количество бит 1 в минутах
Форматирование: {m:02d} — минуты с ведущим нулём

Сложность:

Время: O(1) — фиксированное количество итераций
Память: O(1)

#Задача 12: XOR Queries of a Subarray (LeetCode 1310) 🟦 Medium

Ссылка: https://leetcode.com/problems/xor-queries-of-a-subarray/

Условие: Дан массив arr и массив запросов queries, где queries[i] = [left, right]. Для каждого запроса вычислите XOR элементов от left до right.

Примеры:

Ввод: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Вывод: [2,7,14,8]
Объяснение:
  [0,1]: 1 ^ 3 = 2
  [1,2]: 3 ^ 4 = 7
  [0,3]: 1 ^ 3 ^ 4 ^ 8 = 14
  [3,3]: 8 = 8

Ограничения:

1 <= arr.length <= 3 × 10⁴
1 <= arr[i] <= 10⁹
1 <= queries.length <= 3 × 10⁴

💡 Подсказка: Используйте префиксный XOR. XOR[left, right] = prefix[right+1] ^ prefix[left].

Решение:

def xorQueries(arr, queries):
    # Префиксный XOR
    prefix = [0]
    for num in arr:
        prefix.append(prefix[-1] ^ num)

    result = []
    for left, right in queries:
        # XOR диапазона = prefix[right+1] ^ prefix[left]
        result.append(prefix[right + 1] ^ prefix[left])

    return result

Объяснение:

prefix[i] = XOR всех элементов arr[:i]
XOR[left, right] = prefix[right+1] ^ prefix[left]
Свойство: a ^ a = 0, поэтому prefix[left] сокращает лишние элементы

Сложность:

Время: O(n + q), где n = len(arr), q = len(queries)
Память: O(n)

#4. Трюки

# Проверка на степень двойки
n > 0 and (n & (n - 1)) == 0

# Убрать младший 1
n &= n - 1

# Получить младший 1
n & -n

# Проверить чётность
n & 1 == 0

# Умножить на 2
n << 1

# Разделить на 2
n >> 1

# Проверить бит i
(n >> i) & 1

# Установить бит i
n | (1 << i)

# Сбросить бит i
n & ~(1 << i)

# Инвертировать бит i
n ^ (1 << i)

#5. Шпаргалка

Задача	Трюк
Single Number	XOR всех элементов
Number of 1 Bits	n &= n-1
Counting Bits	dp[i] = dp[i>>1] + (i&1)
Reverse Bits	Сдвиги 32 раза
Missing Number	XOR индексов и значений
Sum of Two Integers	XOR + AND << 1
Range Bitwise AND	Общий префикс
Find Difference	XOR всех символов
Power of Two	n & (n-1) == 0
Maximum XOR	Жадный по битам
Binary Watch	Перебор + count('1')
XOR Queries	Префиксный XOR

#6. ⚠️ Common Mistakes

#❌ Ошибка 1: Непонимание XOR

Проблема: Не знают свойства XOR.

# ❌ Неправильно — используют hash set
def singleNumber(nums):
    seen = set()
    for num in nums:
        if num in seen:
            seen.remove(num)
        else:
            seen.add(num)
    return seen.pop()  # O(n) память

# ✅ Правильно — XOR
def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result  # O(1) память!

Почему это неправильно: XOR использует O(1) памяти.

#❌ Ошибка 2: Забыли n > 0 для проверки степени двойки

Проблема: 0 & (0-1) = 0, но 0 не степень двойки.

# ❌ Неправильно
def isPowerOfTwo(n):
    return (n & (n - 1)) == 0  # 0 вернёт True!

# ✅ Правильно
def isPowerOfTwo(n):
    return n > 0 and (n & (n - 1)) == 0

Почему это неправильно: 0 не является степенью двойки.

#❌ Ошибка 3: Неправильный сдвиг для отрицательных чисел

Проблема: >> сохраняет знак.

# ❌ Неправильно
n = -8
n >> 1  # -4 (знак сохраняется)

# ✅ Правильно — используйте >>> для логического сдвига
# В Python нет >>>, но можно использовать маску
n & 0xFFFFFFFF  # Беззнаковое представление

Почему это неправильно: Арифметический сдвиг сохраняет знак.

#❌ Ошибка 4: Пропуск проверки границ

Проблема: Не проверяют n <= 0.

# ❌ Неправильно
def hammingWeight(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count
# Для отрицательных n бесконечный цикл!

# ✅ Правильно
def hammingWeight(n):
    count = 0
    n = n & 0xFFFFFFFF  # Беззнаковое
    while n:
        n &= n - 1
        count += 1
    return count

Почему это неправильно: Отрицательные числа в дополнении до 2.

#❌ Ошибка 5: Неправильное использование приоритета операторов

Проблема: & имеет меньший приоритет, чем ==.

# ❌ Неправильно
if n & 1 == 0:  # n & (1 == 0) = n & 0 = 0!

# ✅ Правильно
if (n & 1) == 0:  # Сначала &, потом ==

Почему это неправильно: Приоритет операторов.

#7. 🎯 Попробуйте сами

#Задача для самостоятельного решения

Условие: Дан целый массив, где каждый элемент встречается дважды, кроме одного. Найдите уникальный элемент.

Пример:

Ввод: nums = [4,1,2,1,2]
Вывод: 4

💡 Подсказка 1

Используйте свойство XOR: a ^ a = 0

💡 Подсказка 2

XOR всех элементов сократит пары

💡 Подсказка 3

a ^ 0 = a

✅ Решение

def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

# Пример:
# [4,1,2,1,2]
# 0 ^ 4 = 4
# 4 ^ 1 = 5
# 5 ^ 2 = 7
# 7 ^ 1 = 6  (1 сократился)
# 6 ^ 2 = 4  (2 сократился)
# return 4

Объяснение:

XOR ассоциативен и коммутативен
Пары сокращаются: a ^ a = 0
Остаётся уникальный: 0 ^ unique = unique

Сложность:

Время: O(n)
Память: O(1)

#8. Заключение

Bit Manipulation даёт O(1) или O(log n) решения.

Ключевые свойства:

a ^ a = 0, a ^ 0 = a
n & (n-1) убирает младший 1
n & -n получает младший 1
XOR для поиска уникального/пропущенного

Операция

Обозначение

Пример

Результат

AND

5 & 3

1 (101 & 011 = 001)

5 | 3

7 (101 | 011 = 111)

XOR

5 ^ 3

6 (101 ^ 011 = 110)

NOT

-6 (дополнение до 2)

Left Shift

5 << 1

10 (101 << 1 = 1010)

Right Shift

5 >> 1

2 (101 >> 1 = 10)

nums = [4, 1, 2, 1, 2] XOR всех элементов: 4 ^ 1 ^ 2 ^ 1 ^ 2 Группируем: 4 ^ (1 ^ 1) ^ (2 ^ 2) 4 ^ 0 ^ 0 4 Пары сократились, остался уникальный элемент!

Ввод: n = 00000010100101000001111010011100 Вывод: 964176192 (00111001011110000010100101000000) Ввод: n = 11111111111111111111111111111101 Вывод: 3221225471 (10111111111111111111111111111111)

Ввод: left = 5, right = 7 Вывод: 4 Объяснение: 5 & 6 & 7 = 101 & 110 & 111 = 100 = 4 Ввод: left = 0, right = 0 Вывод: 0 Ввод: left = 1, right = 2147483647 Вывод: 0

n = 8 (1000 в двоичной) n - 1 = 7 (0111 в двоичной) n & (n-1): 1000 (8) & 0111 (7) ------ 0000 (0) ← степень двойки! n = 6 (110 в двоичной) n - 1 = 5 (101 в двоичной) n & (n-1): 110 (6) & 101 (5) ----- 100 (4) ← не 0, не степень двойки!

Задача

Трюк

Single Number

XOR всех элементов

Number of 1 Bits

n &= n-1

Counting Bits

dp[i] = dp[i>>1] + (i&1)

Reverse Bits

Сдвиги 32 раза

Missing Number

XOR индексов и значений

Sum of Two Integers

XOR + AND << 1

Range Bitwise AND

Общий префикс

Find Difference

XOR всех символов

Power of Two

n & (n-1) == 0

Maximum XOR

Жадный по битам

Binary Watch

Перебор + count('1')

XOR Queries

Префиксный XOR