代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
将整数转换为二进制字符串并计数。
PHP解决方案:
substr_count(decbin($integer), '1');
其他回答
对于那些想要在c++ 11中为任何无符号整数类型作为consexpr函数的人(tacklelib/include/tacklelib/utility/math.hpp):
#include <stdint.h>
#include <limits>
#include <type_traits>
const constexpr uint32_t uint32_max = (std::numeric_limits<uint32_t>::max)();
namespace detail
{
template <typename T>
inline constexpr T _count_bits_0(const T & v)
{
return v - ((v >> 1) & 0x55555555);
}
template <typename T>
inline constexpr T _count_bits_1(const T & v)
{
return (v & 0x33333333) + ((v >> 2) & 0x33333333);
}
template <typename T>
inline constexpr T _count_bits_2(const T & v)
{
return (v + (v >> 4)) & 0x0F0F0F0F;
}
template <typename T>
inline constexpr T _count_bits_3(const T & v)
{
return v + (v >> 8);
}
template <typename T>
inline constexpr T _count_bits_4(const T & v)
{
return v + (v >> 16);
}
template <typename T>
inline constexpr T _count_bits_5(const T & v)
{
return v & 0x0000003F;
}
template <typename T, bool greater_than_uint32>
struct _impl
{
static inline constexpr T _count_bits_with_shift(const T & v)
{
return
detail::_count_bits_5(
detail::_count_bits_4(
detail::_count_bits_3(
detail::_count_bits_2(
detail::_count_bits_1(
detail::_count_bits_0(v)))))) + count_bits(v >> 32);
}
};
template <typename T>
struct _impl<T, false>
{
static inline constexpr T _count_bits_with_shift(const T & v)
{
return 0;
}
};
}
template <typename T>
inline constexpr T count_bits(const T & v)
{
static_assert(std::is_integral<T>::value, "type T must be an integer");
static_assert(!std::is_signed<T>::value, "type T must be not signed");
return uint32_max >= v ?
detail::_count_bits_5(
detail::_count_bits_4(
detail::_count_bits_3(
detail::_count_bits_2(
detail::_count_bits_1(
detail::_count_bits_0(v)))))) :
detail::_impl<T, sizeof(uint32_t) < sizeof(v)>::_count_bits_with_shift(v);
}
谷歌测试库中的附加测试:
#include <stdlib.h>
#include <time.h>
namespace {
template <typename T>
inline uint32_t _test_count_bits(const T & v)
{
uint32_t count = 0;
T n = v;
while (n > 0) {
if (n % 2) {
count += 1;
}
n /= 2;
}
return count;
}
}
TEST(FunctionsTest, random_count_bits_uint32_100K)
{
srand(uint_t(time(NULL)));
for (uint32_t i = 0; i < 100000; i++) {
const uint32_t r = uint32_t(rand()) + (uint32_t(rand()) << 16);
ASSERT_EQ(_test_count_bits(r), count_bits(r));
}
}
TEST(FunctionsTest, random_count_bits_uint64_100K)
{
srand(uint_t(time(NULL)));
for (uint32_t i = 0; i < 100000; i++) {
const uint64_t r = uint64_t(rand()) + (uint64_t(rand()) << 16) + (uint64_t(rand()) << 32) + (uint64_t(rand()) << 48);
ASSERT_EQ(_test_count_bits(r), count_bits(r));
}
}
你要找的函数通常被称为二进制数的“横向和”或“总体数”。Knuth在前分册1A,第11-12页中讨论了它(尽管在第2卷,4.6.3-(7)中有简要的参考)。
经典文献是Peter Wegner的文章“二进制计算机中的一种计数技术”,摘自ACM通讯,卷3(1960)第5号,第322页。他给出了两种不同的算法,一种针对“稀疏”(即1的数量很少)的数字进行了优化,另一种针对相反的情况。
int countBits(int x)
{
int n = 0;
if (x) do n++;
while(x=x&(x-1));
return n;
}
或者:
int countBits(int x) { return (x)? 1+countBits(x&(x-1)): 0; }
在我最初的回答7年半之后,@PeterMortensen质疑这是否是有效的C语法。我发布了一个在线编译器的链接,显示它实际上是完全有效的语法(代码如下)。
#include <stdio.h>
int countBits(int x)
{
int n = 0;
if (x) do n++; /* Totally Normal Valid code. */
while(x=x&(x-1)); /* Nothing to see here. */
return n;
}
int main(void) {
printf("%d\n", countBits(25));
return 0;
}
输出:
3
如果你想重新写清楚,它看起来是这样的:
if (x)
{
do
{
n++;
} while(x=x&(x-1));
}
但在我看来,这太过分了。
然而,我也意识到函数可以变得更短,但可能更神秘,写为:
int countBits(int x)
{
int n = 0;
while (x) x=(n++,x&(x-1));
return n;
}
一个简单的算法来计算设置位的数量:
int countbits(n) {
int count = 0;
while(n != 0) {
n = n & (n-1);
count++;
}
return count;
}
以11(1011)为例,尝试手动运行该算法。它应该对你有很大帮助!
Python的解决方案:
def hammingWeight(n: int) -> int:
sums = 0
while (n!=0):
sums+=1
n = n &(n-1)
return sums
在二进制表示中,n中最不有效的1位总是对应n - 1中的0位。因此,对n和n - 1这两个数进行and运算总是将n中最不有效的1位翻转为0,并保持所有其他位相同。