[C++] 2개 이하로 다른 비트 ★★

2개 이하로 다른 비트

난이도 ★★

 

문제

---

 

내 풀이

---

규칙찾기

■ 짝수

•  0을 포함한 2, 4, 6,... 짝수들은 비트로 표현했을 때, 가장 오른쪽 비트는 항상 0이다. 가장 오른쪽 비트는 2^0 = 1에 대응하며, 그 외 나머지 비트들은 모두 2^i으로 짝수이기 때문이다. 가장 오른쪽 비트가 1이면  + 1이 된다는 것이므로 그 비트는 무조건 홀수가 될 수 밖에 없다.
• 따라서 짝수인 수 2n들의 f 값은 언제나 2n + 1이다. 가장 오른쪽 비트가 0이기에 1을 더해주면 '올림'없이 총 1개의 비트만 다르게 된다.

■ 홀수

• 짝수와 달리 홀수를 비트로 표현하면 가장 오른쪽 비트가 무조건 1이다.
• 그렇기 때문에 홀수는 더했을 때의 '올림'을 생각해야 한다. 1만 더해주어도 "최소 2개의 비트"가 달라지기 때문이다. 01 -> 10
• 여기서 규칙은 오른쪽에서부터 연속된 1의 비트의 개수가 f값과 연관이 있는것이다. 위 문제 예시에서 7을 살펴보자 먼저 7은 비트로 0111 이며 f값을 찾고자 하면 1011이 되어야한다. 
• 즉, 연속된 비트의 개수가 n개라고 할 때, n 자리만 1이고 나머진 0인 수를 더한게 f값이 된다. 0111의 f값은 0100을 더한 값 

#include <string>
#include <vector>

using namespace std;

// f(x) 의 정의 x보다 크고, x와 비트가 1~2개 다른 수들 중에서 제일 작은 수
vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    // 주어진 정수보다 큰 수부터 +1 씩 다른 비트의 개수가 2개 이하인 수를 찾아라
    // 짝수: f(x) = x + 1
    // 홀수: x의 연속된 1의 비트의 개수가 n개라고 할 때, n - 1자리의 비트 수만큼 더해진게 f값이 된다
    // ex) 101111 의 f값은 000111를 더한 값이 된다
    for (auto& n : numbers) {
        if (n % 2 == 0) { // 짝수
            answer.push_back(n + 1);
        } else { // 홀수
            long long bit = 1;
            // 가장 오른쪽부터 차례로 n 개의 연속된 1 로 이루어진 비트구하기
            while (true) {
                if ((n & bit) == 0) break;
                bit *= 2; // 곱하기 2 를 하면 다음 비트로
            }
            bit = bit / 2;
            answer.push_back(n + bit);
        }
    }
    
    return answer;
}