__builtin_popcount 관련 문제

1. 점프와 순간 이동

https://school.programmers.co.kr/learn/courses/30/lessons/12980

프로그래머스

 

위 문제를 풀면서, 나는 input으로 받은 수를 계속 2로 나누며 나머지가 생기는 횟수를 카운트했다.

그런데 다른 사람 풀이에서 __builtin_popcount 함수를 이용해 코드 한 줄로 문제를 해결할 수 있다는 것을 알게 되었다.

#include <iostream>
using namespace std;

int solution(int n) {
    return __builtin_popcount(n);
}

__builtin_popcount(n)란 입력으로 받은 수를 이진수로 표현했을 때, 해당 수가 가진 1의 수를 세어 주는 함수이다.

예를 들어 n이 13이라면, 이진수로 1101이므로 3을 반환하는 방식이다.

이때 2로 나눈다는 것은 해당 이진수를 오른쪽으로 1회 시프트 연산을 하는 것과 마찬가지이고, 그 때의 마지막 자리수가 1이라면 해당 숫자는 홀수이므로 2로 나눴을 때 나머지가 생기는 상황과 동일하다.

 

 

 

해당 함수를 알게 된 이후로 종종 비슷한 문제를 풀게 될 때마다 잘 사용하고 있어서, 예시를 아래 정리해 둔다.

(참고: visual studio는 프로그래머스(gcc)와 다른 환경(msvc)을 사용하기 때문에 __popcnt 함수를 사용한다고 한다)

 

 

2. 다음 큰 숫자

https://school.programmers.co.kr/learn/courses/30/lessons/12911

프로그래머스

 

이 문제는 아예 문제에서부터 이진수로 변환했을 때의 1의 개수를 언급한다.

주어진 숫자의 이진수와 1의 개수가 같으면서 다음으로 큰 숫자를 구하는 문제이다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = n+1; //answer는 n보다 무조건 크기 때문에 +1
    
    while(1)
    {
    	//주어진 숫자 n과 answer의 이진수의 1의 개수가 같아질 때까지 answer에 1을 더한다
    	//처음으로 이진수의 1의 개수가 같아진 순간이 정답이다
        if(__builtin_popcount(answer) == __builtin_popcount(n))
            break;
        answer++;
    }
    
    return answer;
}

 

 

 

3. 배열의 길이를 2의 거듭제곱으로 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/181857

프로그래머스

 

주어진 vector의 길이가 2의 정수 거듭제곱이 될 때까지 뒤에 0을 추가하여 출력하는 문제이다.

2의 제곱수는 가장 큰 자리수 하나만 1일 때임을 이용한다. (4 = 0010 (2), 32 = 0010 0000 (2) 등)

#include <vector>

using namespace std;

vector<int> solution(vector<int> arr) {  
	//arr 사이즈의 이진수의 1의 개수가 1이 될 때까지 0을 추가한다
    while(__builtin_popcount(arr.size()) != 1)
        arr.push_back(0);
    
    return arr;
}

 

 

 

4. 막대기

https://www.acmicpc.net/problem/1094

1094번: 막대기

2의n제곱들을 하나씩만 더해 특정 수를 만드는 문제이므로 점프와 순간이동과 같은 원리이다.

#include <iostream>

using namespace std;

int main()
{
    int num;
    cin >> num;
    
    cout << __builtin_popcount(num);
    
    return 0;
}

 

 

 

5.  물병

https://www.acmicpc.net/problem/1052

1052번: 물병

가장 적은 수로 만든 물병의 갯수가 곧 이진수로 표현했을 때 1의 갯수와 같기 때문에 1씩 더하면서 조건값보다 1의 갯수가 작아질 때까지 반복하면 된다.

#include <iostream>

using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;

    int answer = 0;

    while (__builtin_popcount(N) > K)
    {
        answer++;
        N++;
    }

    cout << answer;

    return 0;
}