[Codility] Count Conforming Bitmasks

 

[Codility] Count Conforming Bitmasks

 

https://app.codility.com/programmers/trainings/9/count_conforming_bitmasks/start/

Codility

---

 

해결전략

 

비트마스크 Bitmask

비트연산자

 

 

주어진 정수 A, B, C 중 적어도 하나에 conform하는 다른 정수의 개수를 찾아야 한다. 

 

conform이라는 것은?

주어진 정수의 비트 중 하나라도 1이면, conform하는 정수의 해당 비트도 1이어야 한다.

A와 B가 있을 때, A가 B에 conform한다는 것은, B의 모든 1 비트에서 A의 해당 비트도 1이라는 것을 의미한다. 즉, B의 0 비트는 A에서 0이거나 1일 수 있다.

주어진 정수에서 0 비트의 개수를 세면, 그 위치에는 0이나 1이 올 수 있다. 이는 2의 거듭제곱 형태 구할 수 있다.

ex. 만약 주어진 정수에서 0 비트가 5개라면, 그 정수에 conform하는 다른 정수는 2^5, 즉 32개다.

---

 

정답코드

 

#include <cmath>

int countZeroBits(int n) // '0' 비트의 개수를 세는 함수
{
    int cnt = 0;

    for (int i = 0; i < 30; i++) // 30비트까지 확인
    {
        if ((n & (1 << i)) == 0) {
            cnt++;
        }
    }

    return cnt;
}

int solution(int A, int B, int C) {
    int a_cnt = countZeroBits(A);
    int b_cnt = countZeroBits(B);
    int c_cnt = countZeroBits(C);
	// 두 정수를 OR 연산한 결과에서 '0' 비트의 개수 계산
    int ab_cnt = countZeroBits(A | B);
    int bc_cnt = countZeroBits(B | C);
    int ac_cnt = countZeroBits(A | C);
	// 세 정수를 OR 연산한 결과에서 '0' 비트의 개수 계산
    int abc_cnt = countZeroBits(A | B | C);

    int answer = pow(2, a_cnt) + pow(2, b_cnt) + pow(2, c_cnt) - pow(2, ab_cnt) - pow(2, bc_cnt) - pow(2, ac_cnt) + pow(2, abc_cnt);
    
    return answer;
}

 

 

---