반응형

 no time long see. 이번 시간에는 c++20부터 적용된 bit 안에 있는 popcount 메소드에 대해 알아봅시다. 사실 코딩 테스트에서 켜진 비트수를 세는 문제, 혹은 이를 응용한 문제가 왕왕 보이는 편이기도 하고요. 그리고 그 이전에는 어떻게 해야 했는지 보도록 하겠습니다.

 


 popcount 메소드는, unsigned integer 형에 대해서만 동작합니다. 어떻게 동작하나만 보도록 하겠습니다.

 

 

 7번째 줄에, popcount(i)가 있는데요. 이는 15에서 켜진 비트 수를 세라는 의미입니다. 몇 개인가요? 4개입니다.

 

 

 따라서, 4가 출력됩니다.

 

 

 예제 2번을 보시면, for loop를 돌면서 i의 켜진 비트 수가 몇 개인지를 출력합니다. 6번째 줄에서 for loop를 보면, i가 int형으로 선언되어 있어요. 이것은 unsigned 형이 아닙니다. 따라서 popcount를 적용하려면, unsigned int형으로 형변환을 시켜줘야 합니다.

 

 

 그러면, 우리가 원하는 대로 값이 잘 나왔음을 볼 수 있어요. 일례로 5는 2진수로 표현하면 101인데, 켜진 비트가 2이므로, popcount 메소드는 2가 나와야 합니다.

 

 

 이제 음수가 아닌, long long형 범위 내에 들어오는 수에 대해서도 켜진 bit 수를 세 보겠습니다. x는 2^40 + 2^30 + 2^10입니다. 즉, 40번째 비트, 30번째 비트, 10번째 비트가 켜졌습니다. 결과는 3이 나와야 합니다. 9번째 줄에, ull로 형변환한 x의 popcount 값을 출력하는데요.

 

 

 3이 나옵니다. 편리하죠?

 

 


 c++2a 이전에는 컴파일러에 따라서 __builtin_popcount 함수를 제공합니다.

 

 예를 들어, 20의 켜진 비트 수는 10100이므로, 2개가 나올 겁니다. 그래서 이 프로그램의 결과는 20 : 2가 나올 겁니다.

 

 

 정말 그렇네요. 그런데, long long형의 경우에는 이야기가 달라집니다.

 

 

 예를 들어 2^35 + 2^30을 생각해 봅시다. 이것은 354억을 넘어가는, 그러니까 int형이나 unsigned int형의 최댓값을 아득히 넘어가는 범위입니다. 이것은 원래대로라면 비트가 2개 켜졌다는 결과가 나와야 합니다.

 

 

 그런데 하나만 켜졌다고 나왔습니다? 이는 popcount가 int 계열에 대해서 동작하기 때문입니다. 차라리, 이런 경우에는 popcountll을 쓰시는 것이 낫습니다. 아래 프로그램을 봅시다.

 

 

 요렇게 쓰면 제대로 출력될까요? 제대로 출력되려면, 켜진 비트 수가 2가 나와야 합니다. 35번째 bit랑 30번째 bit가 켜졌다고 해야 하기 때문입니다.

 

 

 의도대로 나오네요. 만약에, 이러한 것들이 없다고 나온다면 답은 하나입니다. 직접 함수를 구현하시면 됩니다.

 

 63번째 bit부터 0번째 bit까지 돌면서 켜져 있는지만 검사합니다. 그러면, 복잡도는 O(log(x))가 됩니다.

반응형

댓글을 달아 주세요