7 ms·
gcc and clang both provide a builtin for this, __builtin_popcount. There are a bunch of other useful things like that too: https://gcc.gnu.org/onlinedocs/gcc/O
by mikeash 10y ago
gcc and clang both provide a builtin for this, __builtin_popcount. There are a bunch of other useful things like that too:
https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
Of course, that doesn't save you from writing the long version if you need portable code, but it's a step in the direction you describe.
- psuter 10y agoMake sure to use __builtin_popcountl to count bits in a uint64_t, or you may miss half of them (yes it happened to me).
- nightcracker 10y agoI love this example. Even though you are aware how error-prone this is, you still get it wrong. long is 32-bits on GCC 32-bit. So it will still give the wrong result with `uint64_t`. You should be using __builtin_popcountll. (don't get me wrong - you're not stupid, it happened to me too: https://github.com/orlp/libop/issues/1 https://github.com/orlp/libop/issues/1)
- psuter 10y agoGood catch, thanks. (It has been a while since I've been on a 32bit platform.)
- lisper 10y ago> it's a step in the direction you describe. Well, sort of. This is not about any one particular optimization. This is about the general pattern of having one human take a high-level concept (like counting bits) and reducing it to a low-level implementation, and then having a second human writing a compiler which tries to reverse-engineer the work that the first human did in order to figure out that they were trying to count bits so that it can emit code that actually does the Right Thing. So yes, __builtin_popcount does improve the situation a little bit, but it perpetuates a whole host of other problems. For example: 1. It has the wrong name. The right name for a function that counts bits is "bitcount", not "popcount" (and certainly not __builtin_popcount!) The __builtin is there because C doesn't have a proper name spacing system, and so using __builtin_popcount perpetuates that problem in the same way that clever compiler optimizations perpetuate other bad aspects of C's design. 2. __builtin_popcount only works on unsigned ints. If you want to count bits in anything else (a string, say, or a bignum) you're back to square 1. To really fix this problem you need a general mechanism for expressing high-level concepts that a compiler can now about and optimize directly. For that, C is completely hopeless. You need a new language.
- rjeli 10y agoI would expect `bitcount` to mean sizeof(x)*8. Population count or Hamming weight is the canonical name for this operation.
- to3m 10y agoErm - ``sizeof x*CHAR_BIT'' ;)
- andreasvc 10y agoA bit is a binary digit, with a value of 0 or 1. Popcount counts the number of 1-bits; and, as said, population count actually is the canonical name. You can apply __builtin_popcount in a loop if you want to count bits in multiple words. The point of exposing this particular operation for an unsigned int is that a recent CPU will likely have an efficient operation for it. Operating on larger units is something better left to your own code or a library. You're definitely not "back to square 1", because the intrinsic offers you an operation that would otherwise only be accessible with inline assembly.
- WalterBright 10y ago> a general mechanism for expressing high-level concepts functions > that a compiler can now about and optimize directly. For that, C is completely hopeless. This has been done with C for generations, i.e. memcpy, strlen, sqrt, and even printf are recognized by the C compiler and custom code is generated. The only problem is the C community has been slow to standardize on additional functions.
- lisper 10y agoNo, that's not the only problem, it's one of many problems. But even by itself it's a pretty frickin' substantial problem.
- WalterBright 10y agoIt means a new language is not required. Even without a Standard update, the various C compiler vendors could get together and agree on a set of them, making a "technical report". Anyhow, what other problems?
- greg7mdp 10y agoThat's the whole point, even from the long version, clang figured out that it was doing a popcount and emited a single popcntq instruction. Nice!
- _RPM 10y agoPop count returns the number of set bits. So it most useful for figuring out if a number is a power of two. If there are more than 1 "set" bits, then it is NOT a power of two. However, a non portable way of determining how many bits are in a object would be this expression, assuming 8 bits are in a byte. `sizeof(object) * 8`
- mikeash 10y agoDetecting a power of two is easy with just (x != 0 && (x & x-1) == 0). A portable way of determining how many bits are in an object is sizeof(object) * CHAR_BIT. No reason to use the 8 version.
- _RPM 10y agoThere are most likely many ways to check if a number is a power of two. I'm not sure if my solution is more efficient. It seems your expression would create more code than mine.