[일반] 파이썬에서 이진수 1개수 O(1)에 어떻게 구하나요?

[익명(223.62)]

검색해도 안나오는거같음..ㅠㅠ

- dc official App

[익명(106.102)]

popcnt라는 intrinsic을 쓰면 됨. gcc에서는 __builtin_popcount인듯

[익명(223.62)]

파이썬에서 다운없이 되나요? - dc App

[익명(58.238)]

아 C 아니고 파이썬이구나 ㅈㅅㅈㅅ
파이썬에서는
https://docs.python.org/3/library/stdtypes.html#int.bit_count
근데
decimal type에서는 안됨 int type에서만 됨

[익명(223.62)]

감사합니다! 혹시 시간복잡도를 알수 있을까요? - dc App

[익명(58.238)]

python int는 크기가 64비트로 고정이니까 O(1)인데 상수시간이라도 직접 세는 것보다는 빠를듯? 직접 재보진 않음 decimal type에서는 O(length).

[C751AE30C787(114.203)]

못 구함 bin(a).count('1')이 최선임 최신은 뭐 있던거 같기도 한데 int형식 설명에서 찾아보셈