Количество установленных битов

Легкая
easy , bit manipulation
06 August 2024

Описание задачи #

Напишите функцию, которая принимает положительное целое число и возвращает количество установленных битов (равных 1) в его двоичном представлении.

Количество установленных битов также называется весом Хэмминга.

Ограничения #

Примеры #

  • Входные данные: n = 11

    Ответ: 3

    Объяснение: В двоичном представлении число имеет в общей сложности три установленных бита — 1011.

  • Входные данные: n = 128

    Ответ: 1

    Объяснение: В двоичном представлении число имеет в общей сложности один установленный бит — 10000000.

  • Входные данные: n = 2147483645

    Ответ: 30

    Объяснение: В двоичном представлении число имеет в общей сложности тридцать установленных битов — 1111111111111111111111111111101.

Решение через подсчет популяции (Pop Count) #

В качестве первого решения рассмотрим наиболее интуитивно понятный способ — буквально посчитать, сколько есть единиц в двоичном представлении числа. Такой способ называется подсчетом популяции, он же — pop count.

Однако, чтобы не приводить каким-то специальным способом число в двоичное представление, а потом итерироваться по каждому биту, мы, как всегда, воспользуемся хитростью.

Из условия задачи мы знаем, что n может иметь значения в диапазоне от 1 до 231 - 1. Это означает, что мы рассматриваем 32-битные числа. То есть число n содержит максимум 32 бита.

Теперь возьмем для примера число 13 и представим его в двоичном виде.

13 -> 1101

Чтобы понять, равен ли определенный бит в числе единице, этот бит нужно умножить на 1 и посмотреть на результат. Если результат равен 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 три установленных бита.

Остался последний вопрос. Как сдвигать единицу в маске? Для этого мы воспользуемся операцией побитового сдвига влево <<.

Реализация #

  • package number_of_1_bits

func hammingWeightPopCount(n int) int {
	mask := 1
	count := 0

	for i := 0; i < 32; i++ {
		if n&mask != 0 {
			count++
		}
		mask <<= 1
	}

	return count
}

  • export const hammingWeightPopCount = (n: number): number => {
    let mask = 1
    let count = 0

    for (let i = 0; i < 32; i++) {
        if (n & mask) {
            count++
        }
        mask <<= 1
    }

    return count
};

Оценка сложности #

По времени

Так как мы знаем, что число n занимает максимум 32 бита, нам необходимо сделать 32 проверки в цикле. Из-за фиксированного количество итераций можно считать сложность константной, то есть — O(1).

По памяти

O(1) — дополнительная память константна.

Решение через смену младшего установленного бита #

Мы можем сделать предыдущий алгоритм проще и немного быстрее.

Ключевая идея этого решения заключается в том, что при побитовом умножении чисел n и n - 1 младший установленный бит числа n всегда сменяется на 0. При этом все остальные биты остаются неизменными.

Посмотрим на наглядном примере.

Пример смены младшего установленного бита

Вместо проверки каждого бита числа мы неоднократно обращаем наименее значимый единичный бит числа на 0 и добавляем 1 к нашему счетчику. При этом число n мы заменяем на полученный результат побитового умножения.

Как только число n становится равным 0, мы знаем, что в нем больше не осталось единиц. Это означает, что в нашем счетчике count содержится правильное количество единиц, которые были в битовом представлении числа n.

Реализация #

  • package number_of_1_bits

func hammingWeight(n int) int {
	count := 0

	for n != 0 {
		count++
		n &= n - 1
	}

	return count
}

  • export const hammingWeight = (n: number): number => {
    let count = 0

    while (n != 0) {
        count++
        n &= n - 1
    }

    return count
};

Оценка сложности #

По времени

Время выполнения зависит от количества единичных битов в числе n.

В худшем случае все биты n являются единичными. Так как мы знаем, что число n занимает максимум 32 бита, нам необходимо сделать 32 итерации цикла в худшем случае. Из-за фиксированного количество итераций можно считать сложность константной, то есть — O(1).

По памяти

O(1) — дополнительная память константна.

Оригинал задачи на Leetcode
< Предыдущая задача
Следующая задача >