Number of 1 Bits

+10

Дано неотрицательное целое число n. Запишите n в двоичной системе и верните количество цифр 1 в его записи. Это количество также называют числом установленных битов, числом единичных битов или весом Хэмминга. Например, число 6 в двоичной системе — это 110, поэтому в нём два бита со значением 1.

Функция

hammingWeight(n: integer) → integer

ninteger: неотрицательное целое число, которое помещается в знаковое 32-битное целое число
Возвращаетinteger: количество единиц в двоичной записи числа n

Ограничения

0 ≤ n ≤ 2³¹-1

Примеры

Ввод: n = 11
Вывод: 3
Пояснение: 11 в двоичной системе — это 1011, то есть 8 + 2 + 1. Три из четырёх двоичных цифр равны 1, поэтому ответ — 3.

Ввод: n = 128
Вывод: 1
Пояснение: 128 — это 2^7, записанное как 10000000: одна единица, за которой следуют нули, поэтому ответ — 1.

Дополнительный вопрос

Если бы эта функция выполнялась миллионы раз, как можно было бы подсчитать количество битов в 32-битном числе с помощью четырёх обращений к таблице из 256 заранее вычисленных значений?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Просматривайте двоичные разряды n, не создавая строку. Чтение последнего бита и сдвиг его в сторону занимает один шаг на каждый двоичный разряд, до 31. Сброс младшего бита 1 с помощью n & (n-1) занимает один шаг на каждый бит 1 — ровно столько, сколько составляет ответ.

Проверьте последний фрагмент и сдвиньте вправо

Идея

n & 1 — это последняя двоичная цифра n: 1, если n нечётное, 0, если оно чётное. Добавь её к счётчику. Затем n >> 1 удаляет эту цифру и перемещает следующую на последнее место; для неотрицательного числа это деление на 2 с округлением вниз. Для 11, 1011, последние биты равны 1, 1, 0 и 1 по мере того, как n уменьшается до 0: три бита со значением 1.

Цикл останавливается, когда n равно 0, поэтому он не обрабатывает ведущие нули: около log2(n) шагов, 8 для 128 и не более 31. Он хранит только n и счётчик.

Алгоритм

Начни счетчик с 0.
Пока n больше 0, прибавляй n & 1 к счетчику.
Сдвинь n вправо на один бит.
Когда n достигнет 0, верни счетчик.

def hammingWeight(n):
    count = 0
    while n > 0:
        count += n & 1  # the last bit is 1 or 0
        n >>= 1         # drop the last bit
    return count

Сбросьте младший установленный бит с помощью n & (n-1)

Идея

Вычитание 1 превращает младший бит 1 в 0, а все нули ниже него — в 1, оставляя биты выше без изменений. Поэтому n & (n-1) сохраняет старшие биты и сбрасывает младший бит 1: 12 — это 1100, 11 — это 1011, а 1100 & 1011 — это 1000.

Каждый шаг удаляет ровно один бит 1, поэтому ответ — это количество шагов до тех пор, пока n не станет равным 0. Для 128 требуется 1 шаг вместо 8, хотя для 2^31-1 по-прежнему требуется 31 шаг. В Lua 5.1 нет побитовых операторов, поэтому его версия находит младший бит 1 делением пополам и вычитает его; цикл по-прежнему выполняется один раз для каждого бита 1.

Алгоритм

Начни счётчик с 0.
Пока n не равно 0, замени n на n & (n-1).
После каждой замены увеличивай счётчик на 1.
Верни значение счётчика.

def hammingWeight(n):
    count = 0
    while n != 0:
        n &= n - 1  # turn off the lowest 1 bit
        count += 1
    return count

Ловушки и крайние случаи

Цикл while n > 1. Цикл останавливается перед последним битом 1 и возвращает 0 для n = 1.
Деление с плавающей точкой. В JavaScript, Lua и R 11 / 2 равно 5.5, а последующие остатки являются дробными числами. Округляй вниз с помощью Math.floor, math.floor или %/% либо используй сдвиг вместо этого.
Запись n & 1 в Lua 5.1. В нём нет побитовых операторов, поэтому код не компилируется; используй n % 2 и math.floor(n / 2).

Частые вопросы3

Какова временная сложность задачи Number of 1 Bits?

Цикл со сдвигом выполняется один раз для каждой двоичной цифры: O(log n), здесь не более 31 шага. Цикл n & (n-1) выполняется один раз для каждого бита 1: O(k), где k — это ответ. Оба используют O(1) дополнительной памяти.

Есть ли встроенная функция для подсчёта установленных битов?

В большинстве языков есть такая функция, часто реализованная с помощью одной инструкции процессора: Integer.bitCount в Java, __builtin_popcount в GCC, bits.OnesCount в Go, count_ones в Rust и int.bit_count в Python 3.10 и более поздних версиях. На собеседовании напишите цикл и упомяните встроенную функцию.

В чём разница между весом Хэмминга и расстоянием Хэмминга?

Вес Хэмминга числа — это количество единиц в его двоичной записи, и именно это значение возвращает данная задача. Расстояние Хэмминга между двумя числами — это количество битовых позиций, в которых они различаются: подсчитайте количество единичных битов в a ^ b, поскольку XOR устанавливает биты ровно в тех позициях, где числа различаются.

def hammingWeight(n):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

n = 11

Ожидаемый вывод