DSA | 14-й день підготовки до інтерв’ю Google | Завдання 16: 191. Кількість 1 бітів

Вступ

Підрахунок кількості встановлених бітів (1) у бінарному представленні цілого числа — це класична задача (#191 на LeetCode) в комп'ютерних науках. Вона відома як задача ваги Геммінга, є одночасно простою та потужною і перевіряє ваше розуміння побітових операцій. У цій статті ми розглянемо задачу, розберемо оптимізоване рішення та проаналізуємо його ефективність.

Опис задачі

Дано позитивне ціле число n, напишіть функцію, яка повертає кількість встановлених бітів у його бінарному представленні. Це також відомо як вага Геммінга.

Приклад 1:

Вхід:

n = 11

Вихід:

3

Пояснення: Бінарне представлення числа 11 — це 1011, яке містить три встановлені біти.

Приклад 2:

Вхід:

n = 128

Вихід:

1

Пояснення: Бінарне представлення числа 128 — це 10000000, яке містить один встановлений біт.

Приклад 3:

Вхід:

n = 2147483645

Вихід:

30

Пояснення: Бінарне представлення числа 2147483645 — це 1111111111111111111111111111101, яке містить тридцять встановлених бітів.

Обмеження:

• 1≤n≤231−1

Підхід та пояснення

Ключ до ефективного вирішення цієї задачі полягає в розумінні побітової операції AND. Зокрема, ми можемо скористатися властивістю, що n & (n - 1) очищає найменший встановлений біт числа n. Повторно застосовуючи цю операцію, ми можемо підрахувати кількість встановлених бітів за O(k), де k — кількість встановлених бітів.

Покрокове пояснення:

Ініціалізуйте лічильник: Почніть з лічильника ans, який дорівнює 0.

Ітерації, поки n не стане нулем: Поки n не стане нулем, виконуйте наступні кроки:

• Оновіть n за допомогою операції n &= (n - 1). Це очищає найменший встановлений біт у n.
• Збільшуйте лічильник ans на 1.

Поверніть лічильник: Як тільки n стане нулем, лічильник буде містити кількість встановлених бітів.

Реалізація коду

Ось Python-реалізація цього рішення:

class Solution:  
 def hammingWeight(self, n: int) -> int:  
 ans = 0  
 while n:  
 n &= (n - 1) # Очищаємо найменший встановлений біт  
 ans += 1 # Збільшуємо лічильник встановлених бітів  
 return ans

Аналіз складності

• Часова складність: O(k), де k — кількість встановлених бітів у n. Кожна ітерація циклу видаляє один встановлений біт, і цикл виконується k разів.
• Просторова складність: O(1), оскільки ми використовуємо тільки постійну кількість додаткового простору.

Покрокове виконання прикладів

Приклад 1:

Вхід:

n = 11

Виконання:

1. Бінарне представлення: 1011.
2. Ітерація 1: n = 1011, n &= (n - 1) → n = 1010, ans = 1.
3. Ітерація 2: n = 1010, n &= (n - 1) → n = 1000, ans = 2.
4. Ітерація 3: n = 1000, n &= (n - 1) → n = 0, ans = 3.

Вихід:

3

Приклад 2:

Вхід:

n = 128

Виконання:

1. Бінарне представлення: 10000000.
2. Ітерація 1: n = 10000000, n &= (n - 1) → n = 0, ans = 1.

Вихід:

1

Приклад 3:

Вхід:

n = 2147483645

Виконання:

1. Бінарне представлення: 1111111111111111111111111111101.
2. Ітерація 30 разів, очищаючи по одному встановленому біту, поки n = 0.

Вихід:

30

Реальні застосування

1. Мережі: Вага Геммінга використовується в алгоритмах виявлення та виправлення помилок.
2. Криптографія: Часто застосовується в алгоритмах шифрування та хешування.
3. Обробка зображень: Побітові операції часто використовуються в рендерингу та обробці зображень.
4. Стиснення даних: Ефективний підрахунок встановлених бітів може допомогти в схемах кодування.

Висновок

Задача ваги Геммінга є простим, але потужним прикладом того, як побітові операції можуть спростити складні завдання.
Зрозумівши та використовуючи операцію n & (n - 1), ми досягаємо елегантного та ефективного рішення.

Для повної реалізації та подальшого вивчення, ознайомтесь з моїми поданнями:

• LeetCode Submission: Посилання
• GitHub Repository: Посилання

Перекладено з: DSA | Day 14 of Google Interview Preparation Journey | Challenge 16: 191. Number of 1 Bits