__builtin_popcount - Codeforces

→ Обратите внимание

До соревнования
Codeforces Round 986 (Div. 2)
09:25:47
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Codeforces Round 986 (Div 2) - Solution Discussion

Shayan

До начала 11:30:47

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя Madiyar

__builtin_popcount

Автор Madiyar, 10 лет назад, По-английски

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?

c++, __builtin_popcount

Madiyar
10 лет назад
42

Комментарии (35)

Показать архивные | Написать комментарий?

ashashwat

10 лет назад, # |

+83

__builtin_popcount = int
__builtin_popcountl = long int
__builtin_popcountll = long long

→ Ответить

Madiyar

10 лет назад, # ^ |

+20

thank you very much, Now I will use it in right condition.

→ Ответить

ShayanH

10 лет назад, # ^ |

What is long int type?

→ Ответить

wil93

10 лет назад, # ^ |

http://stackoverflow.com/questions/271076/what-is-the-difference-between-an-int-and-a-long-in-c

→ Ответить

a_kk

8 лет назад, # ^ |

can __builtin_popcount work for unsigned long long ???

→ Ответить

yeputons

8 лет назад, # ^ |

Nope, use __builtin_popcountll

→ Ответить

a_kk

8 лет назад, # ^ |

okk thanks

→ Ответить

kalimm

10 лет назад, # |

← Rev. 2 →

-18

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

→ Ответить

Xellos

10 лет назад, # ^ |

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

→ Ответить

kalimm

10 лет назад, # ^ |

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

→ Ответить

Xellos

10 лет назад, # ^ |

+19

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

→ Ответить

kalimm

10 лет назад, # ^ |

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

→ Ответить

waterfall

10 лет назад, # |

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

→ Ответить

blankSpace

10 лет назад, # |

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

→ Ответить

kien_coi_1997

10 лет назад, # ^ |

Is __builtin_popcount slow too much? Or only little?

→ Ответить

blankSpace

10 лет назад, # ^ |

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

→ Ответить

zeliboba

10 лет назад, # ^ |

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

→ Ответить

Zlobober

8 лет назад, # ^ |

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

→ Ответить

3tao1n

8 лет назад, # ^ |

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

→ Ответить

CountZero

8 лет назад, # ^ |

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

→ Ответить

sgtlaugh

8 лет назад, # ^ |

+26

inline int popcount(int x){
    int count = 0;
    __asm__ volatile("POPCNT %1, %0;"
        :"=r"(count)
        :"r"(x)
        :
    );
    return count;
}

→ Ответить

Robur_131

4 года назад, # ^ |

How does the above compare to this approach?

→ Ответить

sgtlaugh

4 года назад, # ^ |

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.

→ Ответить

ashashwat

10 лет назад, # ^ |

__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

→ Ответить

kien_coi_1997

10 лет назад, # ^ |

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

→ Ответить

ivan100sic

4 года назад, # ^ |

+34

It's slow unless you instruct the compiler to use the popcnt instruction.

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
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<n; x++) {
      y += __builtin_popcountll(x);
  }
  
  cout << y << '\n';
}

In all tests, $$$n=10^9$$$.

Without pragmas, running time is 2245 ms.
With just O3, it's 2261 ms.
With just popcnt, it's 623 ms.
With both, it's 421ms.

→ Ответить

AHMADUL

5 лет назад, # |

← 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).

→ Ответить

I_love_Schwifty

5 лет назад, # ^ |

+10

Wow such a fast answer

→ Ответить

AHMADUL

5 лет назад, # ^ |

Hmmm,,,hahaha.

→ Ответить

Letscode_sundar

4 года назад, # ^ |

-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

→ Ответить

collapse

4 года назад, # ^ |

-14

They refer to the same thing. GCC stands for GNU Compiler Collection.

→ Ответить

_runtimeTerror_

4 года назад, # |

Lol same thing happened with me in a codechef contest .. and i couldn't spot it during the whole contest

→ Ответить

dmkz

4 года назад, # ^ |

← Rev. 2 →

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.

→ Ответить

Abhitator216

2 года назад, # |

-13

what is the time complexity of __builtin_popcount() which is used as cpp inbuilt function

→ Ответить

sahaun

2 года назад, # ^ |