28

What is the equivalent to __builtin_popcount as found in GCC and Clang, for MSVC-10?

Matt Joiner
  • 112,946
  • 110
  • 377
  • 526
  • 1
    Link: http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer – Hans Passant Oct 03 '10 at 12:00
  • 1
    Have a look at [these](http://msdn.microsoft.com/en-us/library/bb385231(v=vs.90).aspx) intrinsics (or the [SSE4 version](http://msdn.microsoft.com/en-us/library/bb531475%28v=VS.90%29.aspx)), else you can always use something from [here](http://chessprogramming.wikispaces.com/Population+Count) – Necrolis Oct 03 '10 at 11:25

3 Answers3

25

With this code snippet you get the GCC builtin when building with MSVC :

#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

(Works from Visual Studio 2008).

Mohamed El-Nakeep
  • 6,580
  • 4
  • 35
  • 39
Eric Nicolas
  • 1,507
  • 3
  • 17
  • 24
  • 1
    It's `_MSC_VER` not `__MSC_VER` – lz96 Dec 07 '16 at 01:54
  • 2
    It's not really the equivalent. The function in GCC [will just use](https://stackoverflow.com/questions/51387998/count-bits-1-on-an-integer-as-fast-as-gcc-builtin-popcountint#comment90027394_51387998) its plain x86 assembly, unless being told otherwise with a specific march/instruction set. `__popcnt` in MSVC [is instead](https://learn.microsoft.com/en-us/cpp/intrinsics/popcnt16-popcnt-popcnt64) the literal hardware instruction *popcnt*. – mirh Apr 12 '20 at 22:15
22

Using the comments provided:

Matt Joiner
  • 112,946
  • 110
  • 377
  • 526
  • 3
    Be careful with this; it will not work with ARM CPUs, or x86 CPUs which don't support the ABM instruction set. – nemequ Mar 20 '17 at 20:34
8

The __popcnt intrinsic mentioned above doesn't work on ARM, or even all x86 CPUs (it requires ABM instruction set). You shouldn't use it directly; instead, if you're on x86/amd64 you should use the __cpuid intrinsic to determine at runtime if the processor supports popcnt.

Keep in mind that you probably don't want to issue a cpuid for every popcnt call; you'll want to store the result somewhere. If your code is always going to be single-threaded this is trivial, but if you have to be thread-safe you'll have to use something like a One-Time Initialization. That will only work with Windows ≥ Vista, though; if you need to work with older versions you'll need to roll your own (or use something from a third-party).

For machines without ABM (or if runtime detection isn't worth it), there are several portable versions at Bit Twiddling Hacks (look for "Counting bits set"). My favorite version works for any type T up to 128-bits:

v = v - ((v >> 1) & (T)~(T)0/3);                           // temp
v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);      // temp
v = (v + (v >> 4)) & (T)~(T)0/255*15;                      // temp
c = (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT; // count

If you want a drop-in version you can use the builtin module in portable-snippets (full disclosure: portable-snippets is one of my projects), which should work pretty much anywhere.

Pavel P
  • 15,789
  • 11
  • 79
  • 128
nemequ
  • 16,623
  • 1
  • 43
  • 62
  • 2
    No need to get fancy with CPU detection. Do it before starting any threads, e.g. with a `static const cpuid_result = cpuid();` so it runs at program startup. – Peter Cordes Sep 22 '17 at 08:59
  • Interesting generic version of the popcount bithack. (See https://stackoverflow.com/a/109025/224132 for the canonical Q&A). – Peter Cordes Sep 22 '17 at 09:01