LeetCode Go - 191. Количество бит 1

Это 22-й день моего участия в Gengwen Challenge.Подробности о мероприятии:Обновить вызов

Для лучшего будущего придерживайтесь чистки зубовLeetCode!

тема

Пожалуйста, реализуйте функцию, которая принимает целое число (в виде двоичной строки) и выводит количество единиц в двоичном представлении числа. Например, 9 в двоичном формате — это 1001, а 2 бита — это 1. Поэтому, если вы введете 9, функция выведет 2.

Пример 1:

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

Пример 2:

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

Пример 3:

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

намекать:

输入必须是长度为 32 的 二进制串 。

Решение 1 — Побитовые операции

Идеи решения проблем

мы знаем $n \& (n−1)$ будет $n$ Самый низкий 1 из 1 становится 0, тогда мы можем использовать это свойство для вычисления $n$ Количество единиц в двоичных битах , т.е. до тех пор, пока $n == 0$ Время $n \& (n−1)$ количество операций.

код

func hammingWeight(num uint32) (n int) {
    for ; num > 0; num &= num - 1 {
        n++
    }
    return
}

Результаты

执行用时：0 ms，在所有 Go 提交中击败了 100.00% 的用户
内存消耗：1.9 MB，在所有 Go 提交中击败了 61.94% 的用户

Анализ сложности

временная сложность: $O(logn)$ . Количество циклов равно $n$ Количество единиц в битах в худшем случае $n$ Все биты равны 1.
Сложность пространства: $O(1)$

ссылка на тему

191. Количество бит 1