Количество единичных битов на Java | Очистка установленных битов, доказательство и дополнительные...

Изучите задачу "Количество единичных битов" (LeetCode 191) на Java с помощью Prepflix. Начните с прямого сканирования битовых позиций, выведите n и (n - 1), докажите, что это сбрасывает ровно один установленный бит, проследите примеры и обсудите повторные вызовы, таблицы байтов, Integer.bitCount, знаковость и сложность для фиксированной ширины. Обе реальные работы на Java прошли 598 из 598 тестов. Базовый результат: 0 мс, 42,44 МБ. Сброс установленного бита: 0 мс, 42,04 МБ. Тайм-аут не произошел. Округленные значения времени проверки не подтверждают измеренное ускорение. Обе работы имеют время O(1) и дополнительное пространство O(1) для входных данных типа int фиксированной ширины; сброс использует одну итерацию на каждый установленный бит. РАЗДЕЛЫ 00:00 Количество единичных битов: подсчет битов, а не цифр 00:37 Чтение фактического входного контракта 01:16 Перевод примеров в двоичный код 01:55 Базовая линия следует непосредственно за определением 02:34 Извлечение бита с помощью сдвига и И 03:14 Кодирование полного сканирования битовых позиций 03:52 Трассировка базовой линии на числе одиннадцать 04:33 Базовая линия действительно прошла проверку 05:11 Вычитание единицы изменяет определенный суффикс 05:49 И обнуляет точно младший установленный бит 06:29 Кодирование одной итерации на каждый установленный бит 07:10 Полный пробный запуск: число одиннадцать становится нулем 07:53 Разреженные числа показывают улучшение 08:33 Плотные числа показывают предел 09:16 Доказательство инвариантности цикла 09:58 Завершение и безопасная арифметика 10:38 Внимательно прочтите оптимизированный результат проверки 11:19 Укажите сложность с четким указанием модель 12:03 Дополнение: предварительное вычисление небольших фрагментов 12:44 Дополнение: в Java уже есть bitCount 13:28 Избегайте ловушек сдвига и знаковости 14:12 Краткий обзор и заключительная трассировка практики Практика: https://leetcode.com/problems/number-of-1-bits/ Базовая задача: https://leetcode.com/problems/number-of-1-bits/submissions/2158580463/ Установка и сброс битов: https://leetcode.com/problems/number-of-1-bits/submissions/2158580996/ Java API: https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/lang/Integer.html#bitCount(int) #Java #LeetCode #DSA #BitManipulation #NumberOf1Bits #Prepflix