Сегодня закрепляем с вами материал по битовым манипуляциям и решаем новую задачу.
Сложность: 🟢 Легкая
ℹ️ Описание
Напишите функцию, которая принимает положительное целое число и возвращает его вес Хэмминга.
⚠️ Ограничения
— Значение n находится в диапазоне от 1 до 2^31 - 1
1️⃣ Пример
Входные данные: n = 11
Ответ: 3
Объяснение: В двоичном представлении число имеет в общей сложности три установленных бита — 1011.
2️⃣ Пример
Входные данные: n = 128
Ответ: 1
Объяснение: В двоичном представлении число имеет в общей сложности один установленный бит — 10000000.
3️⃣ Пример
Входные данные: n = 2147483645
Ответ: 30
Объяснение: В двоичном представлении число имеет в общей сложности тридцать установленных битов — 1111111111111111111111111111101.
✅ Решение через подсчет популяции (Pop Count)
В качестве первого решения рассмотрим наиболее интуитивно понятный способ — буквально посчитать, сколько есть единиц в двоичном представлении числа. Такой способ называется подсчетом популяции, он же — pop count. Однако, чтобы не приводить каким-то специальным способом число в двоичное представление, а потом итерироваться по каждому биту, мы, как всегда, воспользуемся хитростью.
Из условия задачи мы знаем, что n может иметь значения в диапазоне от 1 до 2^31 - 1. Это означает, что мы рассматриваем 32-битные числа. То есть число n содержит максимум 32 бита.
Теперь возьмем для примера число 13 и представим его в двоичном виде.
13 -> 1101
Чтобы понять, равен ли определенный бит в числе единице, этот бит нужно умножить на 1 и посмотреть на результат. Если результат равен 1, то и бит тоже равен 1. В противном случае бит равен нулю.
Это определяется правилами побитового умножения. Если в одном операнде всегда стоит единица, то результат операции может быть равен единице только в том случае, если второй операнд тоже равен 1.
0 & 1 = 0
1 & 1 = 1
Это означает, что мы можем пройтись по каждому из 32 битов числа n и умножить его побитово на 1. Если результат равен единице, то мы можем увеличить счетчик установленных битов на 1. После подсчета всех 32 битов мы получим количество установленных битов в счетчике.
Однако встает вопрос, как это сделать. В каждом языке программирования есть операция побитового умножения двух чисел — &. Она берет два числа, побитово их умножает и получает третье число, которое в двоичном представлении является результатом этого побитового умножения.
Мы заведем маску mask, которая на самом деле является целым числом, и счетчик count. Начальное значение mask будет равно 1. Теперь посмотрим на наглядный пример решения.
Представим наше число 13 и маску в двоичном виде и проведем между ними побитовое умножение.
1101 & 0001 = 0001 = 1
В качестве результата получилось положительное число, то есть в первом бите числа n находится единица. Увеличиваем счетчик установленных битов count на 1. Теперь сдвинем единицу в маске на одну позицию влево и сделаем то же самое.
1101 & 0010 = 0000 = 0
В качестве результата получился ноль, то есть во втором бите числа n находится ноль. В этом случае мы не увеличиваем счетчик. Далее используем этот же алгоритм для оставшихся битов.
1101 & 0100 = 0100 = 4
Так в ответе мы получили 4, а не 0, это означает, что на месте единицы в маске в числе n бит также равен единице. Увеличиваем счетчик установленных битов count на 1.
1101 & 1000 = 1000 = 8
По такой же логике мы понимаем, что в старшем бите числа `n` также находится единица. Таким образом мы получили count = 3, то есть в числе n = 13 три установленных бита.
Остался последний вопрос. Как сдвигать единицу в маске? Для этого мы воспользуемся операцией побитового сдвига влево <<.
Посмотреть реализацию в блоге.
🅾️ Оценка сложности
По времени
Так как мы знаем, что число n занимает максимум 32 бита, нам необходимо сделать 32 проверки в цикле. Из-за фиксированного количество итераций можно считать сложность константной, то есть — O(1).
По памяти
O(1) — дополнительная память константна.
#bit_manipulation #easy