标签: bitcount

1 = 0b1 -> 1
5 = 0b101 -> 3
10 = 0b1010 -> 4
100 = 0b1100100 -> 7
1000 = 0b1111101000 -> 10
…

如何获得整数的位长度,即在Python中表示正整数所需的位数？

我感兴趣,这是通过这种方式计算以字节为单位设置的位数的最佳方法

template< unsigned char byte > class BITS_SET
{
public:
    enum {
     B0 = (byte & 0x01) ? 1:0,
     B1 = (byte & 0x02) ? 1:0,
     B2 = (byte & 0x04) ? 1:0,
     B3 = (byte & 0x08) ? 1:0,
     B4 = (byte & 0x10) ? 1:0,
     B5 = (byte & 0x20) ? 1:0,
     B6 = (byte & 0x40) ? 1:0,
     B7 = (byte & 0x80) ? 1:0
    };
public:
 enum{RESULT = B0+B1+B2+B3+B4+B5+B6+B7};
};

也许在运行时知道byte的值是最优的？是否建议在代码中使用它？

获得数字的基数2对数的最佳解决方案是什么,我知道它是2的幂(2^k).(当然,我知道只有价值2^k不k本身).

我想做的一种方法是减去1然后做一个bitcount:

lg2(n) = bitcount( n - 1 ) = k, iff k is an integer
0b10000 - 1 = 0b01111, bitcount(0b01111) = 4

但有没有更快的方法(没有缓存)？还有一些不涉及bitcount的事情会很快知道吗？

其中一个应用是:

suppose you have bitmask
0b0110111000

and value
0b0101010101

and you are interested of
(value & bitmask) >> number of zeros in front of bitmask
(0b0101010101 & 0b0110111000) >> 3 = 0b100010

this can be done with

using bitcount
value & bitmask >> bitcount((bitmask - 1) xor bitmask) - …

我需要解释一下这条特定的线是如何工作的.
我知道这个函数计算1位的数量,但这条线究竟是如何清除最右边的1位？

int f(int n) {
    int c;
    for (c = 0; n != 0; ++c) 
        n = n & (n - 1);
    return c;
}

有人可以简单地向我解释一下或给出一些"证明"吗？

我试图在512MB内存中有多少1个,我找到了两种可能的方法,_mm_popcnt_u64()并且__builtin_popcountll()在gcc内置中.

_mm_popcnt_u64()据说使用CPU介绍SSE4.2,这似乎是最快的,并且__builtin_popcountll()不使用表查找.

所以,我认为__builtin_popcountll()应该慢一些_mm_popcnt_u64().

但是我得到了这样的结果:

两种方法花了几乎相同的时间.我非常怀疑他们用同样的方式工作.

我也得到了这个 popcntintrin.h

/* Calculate a number of bits set to 1. */
extern __inline int __attribute__((__gnu_inline__, __always_inline__, __artificial___))
_mm_popcnt_u32 (unsigned int __X)
{
  return __builtin_popcount (__X);
}

#ifdef __x86_64__
extern __inline long long __attribute__((__gnu_inline__, __always_inline__, __artificial__))
_mm_popcnt_u64 (unsigned long long __X)
{
  return __builtin_popcountll (__X);
}
#endif

所以,我很困惑__builtin_popcountll()地球上的作品

我有一大块内存,比如256 KiB或更长.我想计算整个块中的1位数,或者换句话说:为所有字节添加"种群计数"值.

我知道AVX-512有一个VPOPCNTDQ指令,它计算512位向量中每个连续64位的1位数,而IIANM应该可以在每个周期发出其中一个(如果一个适当的SIMD向量寄存器是可用) - 但我没有任何编写SIMD代码的经验(我更像是一个GPU人).此外,我不是100%确定AVX-512目标的编译器支持.

在大多数CPU上,仍然没有(完全)支持AVX-512; 但AVX-2广泛可用.我无法找到类似于VPOPCNTDQ的低于512位的向量化指令,所以即使理论上我也不确定如何使用支持AVX-2的CPU快速计算位数; 也许这样的事情存在,我只是错过了它？

无论如何,对于两个指令集中的每一个,我都很欣赏一个简短的C/C++函数 - 使用一些内部包装库或内联汇编.签名是

uint64_t count_bits(void* ptr, size_t size);

笔记:

• 与如何在Sandy Bridge上的一系列整数中快速将位数计入单独的箱中相关？,但不是一个骗局.
• 如果重要的话,我们可以假设输入是完全一致的.
• 忘记多个核心或套接字,我想要单个(单个线程)核心的代码.

观看时Matt Godbolt 的演讲时时，我惊讶地发现，如果指示 Clang 针对 Haswell\xc2\xb9 架构进行编译，则会得出以下代码

int foo(int a) {\n    int count = 0;\n    while (a) {\n        ++count;\n        a &= a - 1;\n    }\n    return count;\n}\n

用于计算设置位int（我不知道我自己需要多长时间才能计算出来），所以它只使用该指令：

foo(int):                                # @foo(int)\n        popcntl %edi, %eax\n        retq\n

我想自己尝试一下，但我发现生成的代码是

foo(int):                                # @foo(int)\n        popcntl %edi, %eax\n        cmovel  %edi, %eax\n        retq\n

事实证明，生成的代码在 Clang 10.0.1 和 Clang 11.0.0 之间发生了变化。

为什么较新的 Clang 又发出了一条以前不需要的指令？代码是如此简单，以至于我无法理解多一条指令除了使代码变慢之外还能做什么（即使速度可能非常小，我不知道）。

\xc2\xb9 作为一个附带问题，事实上不指定-march=haswell会导致更长、更人性化的代码这一事实是否仅仅意味着该选项所针对的物理 CPU 具有用于执行设置位计数和其他操作的电路（好吧，不管 clang 默认是什么）不？

我已经看到了关于计算insert type of输入中设置位数的众多问题,但为什么它有用呢？

对于那些寻找有关位计数的算法的人,请看这里:

1. 计算无符号长整数序列中的公共位
2. 计算unsigned int中位转换次数的最快方法
3. 如何计算32位整数中的设置位数？

Bitcounting可以通过多种方式完成,例如.with set bit iterator,unset bit iterator,pre-computed bits with lookup tables或parallel counting.正如我通过搜索网络所发现的那样,当未设置的位数较少时,未设置的位迭代器很快,而相反的位置则设置位迭代器.但是什么时候应该使用并行计数,特别是MIT HAKMEM(见下文)？它似乎相当快,虽然可能比查找表慢.在速度方面,它与set/unset位相比总是更好吗？还有其他一些关于速度和记忆的选择吗？

 int BitCount(unsigned int u) {
     unsigned int uCount;

     uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
     return ((uCount + (uCount >> 3)) & 030707070707) % 63;
 }

我知道这就是代码。但我无法理解它的作用

 `public static int bitCount(long i){
         i = i - ((i  > > > 1) & 0x5555555555555555L);
         i = (i & 0x3333333333333333L) + ((i  > > > 2) & 0x3333333333333333L);
         i = (i + (i  > > > 4)) & 0x0f0f0f0f0f0f0f0fL;
         i = i + (i  > > > 8);
         i = i + (i  > > > 16);
         i = i + (i  > > > 32);
       return (int)i & 0x7f;
 }`