Madiyar's blog

__builtin_popcount
By Madiyar, 5 years ago, In English,

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?

 
 
 
 
  • Vote: I like it
  • +31
  • Vote: I do not like it

Comments Comments (23)
»
5 years ago, # |
  Vote: I like it +83 Vote: I do not like it
  • __builtin_popcount = int
  • __builtin_popcountl = long int
  • __builtin_popcountll = long long
→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

What is " __builtin_popcount"? I found something. But I couldn't find all of them :(

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Funny — I could. http://lmgtfy.com/?q=popcount

    About the 3rd result from the top says "popcount returns the number of non-zero bits in x".

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      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 .

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        Okay, you just said you couldn't find anything.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I changed my reply. But still I don't know "complexity, C++ or C++11, parameters, and works for any compiler?"...

          → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +22 Vote: I do not like it

__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.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Is __builtin_popcount slow too much? Or only little?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't know. Maybe you can tell me :)

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Seems that it is the fastest way to count bits in c++ in general case.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +36 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it -15 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            __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.

            → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +26 Vote: I do not like it 
          inline int popcount(int x){
    int count = 0;
    __asm__ volatile("POPCNT %1, %0;"
        :"=r"(count)
        :"r"(x)
        :
    );
    return count;
}
          → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    __builtin_popcount looks to have O (1) complexity. Here is the proposed improvement [1] and the source code [2], look from line number 808.

    [1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=36041
    [2] https://gcc.gnu.org/viewcvs/gcc/trunk/libgcc/libgcc2.c?view=markup&pathrev=200506

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      O log k (k is number of bit). Because k is specified, the complexity is O(1).

      → Reply