Number of 1 Bits

Лёгкая№191по битам

Дано положительное целое число. Нужно посчитать, сколько его битов равны 1. Наш пример: n = 90 = 1011010 — ответ 4.

191 Number of 1 BitsРазбор · 1×

Пример: n = 90 = 1011010. Каждый раунд сбрасывает младшую 1 в n через n & (n - 1) и считает её.

n= 901011010mn - 1—countнайдено—
бит 1бит 0младшая 1 в nбит, который перевернуло n - 11, которую только что сбросило &посчитанная единица

n = 90 = 1011010: 7 битов. Единиц пока не насчитали

01/19
сначала · назад · пуск · шаг
Скорость
1function hammingWeight(n):
2 count = 0
3 while n != 0:
4 m = n - 1
5 n = n & m // clears the lowest 1
6 count = count + 1
7 return count
состояние
n
90 = 1011010
m
–
count
0
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Вычитание 1 занимает у младшей 1: эта 1 становится 0, нули под ней — единицами, а все биты выше не меняются. Поэтому n & (n - 1) — это n, в котором сброшена ровно младшая 1.
  2. Каждый раунд сбрасывает одну 1 и считает её, а цикл кончается на 0, когда единиц не осталось. Значит, count в конце равен числу единиц.
  3. Цикл идёт по разу на каждую 1, а не на каждый бит: в 90 7 битов, а раундов 4. Чтение по одному биту заняло бы 7 шагов, а на LeetCode — 32.

Сложность

Время O(k), где k — число единиц: по раунду на каждую 1, на LeetCode не больше 32. Память O(1): два числа и счётчик.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.