集合位解的LeetCode计数数

Question

问题-编写一个函数，它接受一个无符号整数，并返回它所拥有的'1‘位数(也称为Hamming重量)。

int hammingWeight(uint32_t n) {
        int count = 0;
        while(n>0){
            count+=n&1;
            n>>=1;
        }
        return count;
    }

你能想出一个更好的方法吗？

一位先生想出了这个

int hammingWeight(uint32_t n) {
    int count = 0;

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

    return count;
}

一个人是如何想出这样的创造性解决方案的？

你对我的解决方案有更好的改进吗？

Answer 1

(由于Code的工作方式，只有您的代码可以被检查。因此，我不会对“一位先生”编写的代码说任何话。

我看到的第一件事是:使用一致的缩进和添加空格。如果您将代码格式化如下，代码的可读性就会大大提高：

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n > 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

另外，在std::uint32_t中使用uint32_t而不是在C++中使用D2可能是个好主意。

您可以将此函数设置为constexpr和noexcept。像这样的简单计算可以在编译时完成，并从内联中获益。

这个函数也可以推广到任何无符号整数类型。模板版本可能如下所示：

template  && std::is_unsigned_v>>
constexpr int hammingWeight(T n) noexcept
{
    // the implementation is the same
}

海事组织的执行情况足够好，而且可读性很强。除非度量揭示了优化的必要性，否则您不必变得非常有创意。

在C++20中，我们有一个标准函数-- std::popcount，在标头中。