While solving Andrew Stankevich Contest 32, Problem K, I noticed that __builtin_popcount for long long doesn't work properly, I spent a lot of time to find my mistake, but when I wrote __builtin_popcount by myself it accepted.

__builtin_popcount defined only for int?

• +31

 » 7 years ago, # |   +83 __builtin_popcount = int __builtin_popcountl = long int __builtin_popcountll = long long
•  » » 7 years ago, # ^ |   +20 thank you very much, Now I will use it in right condition.
•  » » 7 years ago, # ^ |   0 What is long int type?
•  » » » 7 years ago, # ^ |   0
•  » » 5 years ago, # ^ |   0 can __builtin_popcount work for unsigned long long ???
•  » » » 5 years ago, # ^ |   +4 Nope, use __builtin_popcountll
•  » » » » 5 years ago, # ^ |   0 okk thanks
 » 7 years ago, # | ← Rev. 2 →   -18 What is " __builtin_popcount"? I found something. But I couldn't find all of them :(
•  » » 7 years ago, # ^ |   +6 Funny — I could. http://lmgtfy.com/?q=popcountAbout the 3rd result from the top says "popcount returns the number of non-zero bits in x".
•  » » » 7 years ago, # ^ |   -9 It is easy to find what popcount do. But I couldn't find complexity, C++ or C++11, parameters, and works for any compiler? Also I couldn't find it on cplusplus.com .
•  » » » » 7 years ago, # ^ |   +19 Okay, you just said you couldn't find anything.
•  » » » » » 7 years ago, # ^ |   0 I changed my reply. But still I don't know "complexity, C++ or C++11, parameters, and works for any compiler?"...
 » 7 years ago, # | ← Rev. 3 →   +22 __builtin_popcount(x) is a function in C++ returns the number of 1-bits set in an int x. In fact, "popcount" stands for "population count," so this is a function to determine how "populated" an integer is.For example, say we have an int x with value equal to 12. 12 in binary is just 1100, and the rest of the digits are just 0's. So, __builtin_popcount(12) = 2.
•  » » 18 months ago, # ^ |   0 Thanks
 » 7 years ago, # | ← Rev. 2 →   +12 Interesting fact : __builtin_popcount is slow. Can anyone tell the complexity? For a constant time bitcount use this : http://pastie.org/9412225 .Please don't ask me how it works exactly! It'd be useful to add it to your library code :)
•  » » 7 years ago, # ^ |   +5 Is __builtin_popcount slow too much? Or only little?
•  » » » 7 years ago, # ^ |   0 I don't know. Maybe you can tell me :)
•  » » » 7 years ago, # ^ |   +2 Seems that it is the fastest way to count bits in c++ in general case.
•  » » » » 5 years ago, # ^ |   +36 No. The fastest way is to precompute all popcounts for 16-bit parts (for int32 case) or 22-bit parts (for int64 case) and calculate the answer in 2 or 3 bit shifts, array element accesses and summations.
•  » » » » » 5 years ago, # ^ |   -15 Actually __builtin_popcount is faster than so-called array table algorithm (sorry for poor English :), don't know how to express it correctly) is my computer, because the memory reading without cache is slow.
•  » » » » » » 5 years ago, # ^ |   +3 __builtin_popcount should be faster because it compiles into one assembler instruction. But it's not true on codeforces, IIRC MinGW uses bit-shifting algorithm instead.
•  » » » » » 5 years ago, # ^ |   +26 inline int popcount(int x){ int count = 0; __asm__ volatile("POPCNT %1, %0;" :"=r"(count) :"r"(x) : ); return count; } 
•  » » » » » » 18 months ago, # ^ |   0 How does the above compare to this approach?
•  » » » » » » » 16 months ago, # ^ |   0 Well it varies with architecture, compiler flags, SSE enabled/disabled. I don't know of an implementation that dominates the rest all the time. Better to benchmark and see for yourself in the platform of your interest.
•  » » 7 years ago, # ^ |   0 __builtin_popcount looks to have O (1) complexity. Here is the proposed improvement [1] and the source code [2], look from line number 808.
•  » » » 7 years ago, # ^ |   +8 O log k (k is number of bit). Because k is specified, the complexity is O(1).
•  » » » » 18 months ago, # ^ |   0 So, the complexity for a number $n$ is $\mathcal{O}(\log\lfloor{\log_2(n)}\rfloor)$ ? I can't see where is the first $\log$ coming from. Can anybody explain this?
•  » » 11 months ago, # ^ |   +34 It's slow unless you instruct the compiler to use the popcnt instruction. #pragma GCC optimize("O3") #pragma GCC target("popcnt") #include using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(!cin.tie(0)); int n; ll y = 0; cin >> n; for (int x=0; x
•  » » 8 months ago, # ^ |   0 The link is dead, someone who knows what was in it can please update/comment it.Thanks
 » 22 months ago, # | ← Rev. 2 →   -25 There is NO __builtin_popcount in c++, it's a built in function of GCC. The function prototype is as follows: int __builtin_popcount(unsigned int) It returns the numbers of set bits in an integer (the number of ones in the binary representation of the integer).
•  » » 22 months ago, # ^ |   +10 Wow such a fast answer
•  » » » 22 months ago, # ^ |   0 Hmmm,,,hahaha.
•  » » » » 11 months ago, # ^ |   -14 Can you tell me what is the difference between GNU and GCC compilers. Because when i installed vscode I installed compilers from MinGW which had the GCC compilers i believe. But i get confused by GNU
•  » » » » » 11 months ago, # ^ |   -14 They refer to the same thing. GCC stands for GNU Compiler Collection.
 » 16 months ago, # |   +8 Lol same thing happened with me in a codechef contest .. and i couldn't spot it during the whole contest
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 You can use just a bitset<32>(x).count() and bitset<64>(x).count() always. It will be optimized on any online judge, you can check assembly there and you will see only call __popcountdi2 in both cases.
 » 5 months ago, # |   -18 INTEGER => __builtin_popcount() LONG INTEGER => __builtin_popcounl() LONG LONG INTEGER => __builtin_popcountll()