프로그래머스 - 2개 이하로 다른 비트

프로그래머스 - 2개 이하로 다른 비트

일단 시간초과가 날 것을 예상하고, 비트를 하나하나 계산하는 방식으로 풀었다.
당연히 시간초과가 났다.
코드는 굉장히 간단한데, base부터 1씩 커지면서 base와 xor 연산 한다.
right shift를 하면서 1과 and 연산을 한 뒤 1이면 다른 비트인 것.

#include <string>
#include <vector>

using namespace std;

bool find_one_bit(long long base, long long target)
{
    long long num = base ^ target;
    int cnt = 0;
    while(num) {
        if((num & 1) == 1)
            cnt++;
        if(cnt > 2) 
            return false;
        num >>= 1;
    }
    return true;
}
vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for(int i=0;i<numbers.size();i++) {
        long long base = numbers[i];
        long long target = numbers[i] + 1;
        while(1) {
            if(find_one_bit(base, target)) {
                answer.push_back(target);
                break;
            }
            target++;
        }
    }
    return answer;
}

그 결과 TC 10, 11에서 시간초과가 발생했고, 전체적으로 느렸다.

#include <string>
#include <vector>

using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    int size = numbers.size();
    for(int i=0;i<size;i++) {
        long long base = numbers[i];
        long long tmp = 1;
        // 이 while loop을 안돌게 not, xor 등을 이용해서 할 수 있을 것 같은데, 잘 안 떠올라서 일단 이렇게 했다.
        while(1) {
            if((tmp & base) == 0) 
                break;
            tmp <<= 1;
        }
        long long target = base | tmp;
        target = target ^ (tmp >> 1); 
        answer.push_back(target);
    }
    return answer;
}

다음은 비트연산으로 푼 경우다.
짝수는 간단하게 생각하면 +1을 해주면 된다.
홀수는 먼저 base기준으로 1부터 left shift하면서 base보다 큰 2의 지수승을 찾아준다.
그 후, base에 찾은 숫자를 or 연산해준 뒤, 찾은 숫자를 right shift 한 뒤 base에 xor연산을 해준다.
즉, left-most-zero를 찾은 뒤 1로 바꾸고, 그 위치 바로 right를 0으로 해주면 된다.

예를 들어, 7의 경우 0000 0111 이니까 0000 1 0 11
그리고 11의 경우 0000 1011 이니까 00001 1 0 1