[Lv 2] 2개 이하로 다른 비트

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

프로그래머스

 

이 문제는 비트 연산의 특징을 사용한다.

정수 x에 대해 f(x)의 결과가 x보다 크고 비트가 1~2개 다른 수 중 가장 작은 수를 찾아야한다.

 

f(x) 함수의 특징은 홀수와 짝수인 경우 분리되어 나타난다.

 

먼저 짝수인 경우, 마지막 비트가 0인 수이다.

따라서 짝수인 경우에 가장 작은 수는 마지막 비트를 1 올리면 된다.

 // 짝수의 경우 n + 1
// 2 -> 3, 4 -> 5
if(x % 2 == 0){
    return x + 1;
}

 

그런데 홀수인 경우 짝수와 달리 마지막 비트가 1이 된다.

따라서 가장 작은 수의 비트가 1개 달라지는 경우와 2개 달라지는 경우가 발생한다.

홀수의 경우 비트의 올림 연산을 사용한다.

 

올림 연산을 사용하면 가장 오른쪽 비트가 0이 되어 왼쪽 비트들의 수가 바뀐다. (01 -> 10)

따라서 최소 2자리의 비트를 바꿀 수 있다.

예를 들어 101111 이라는 값이 있을때 f함수의 결과로 110111이 되어야한다.

즉, 연속된 1 비트의 개수가 n개라고 할 때 n - 1자리의 비트수 만큼 더해진 것이 f값이라고 할 수 있다.

101111의 f 값은 001000이 된다.

 

정리하면, 홀수인 경우 비트 연산자인 &연산자를 사용한다.

bit를 다음 비트로 계속 올리면서 &연산자의 결과가 0인 경우까지 증가시킨다.

&연산자의 0인 경우 모든 비트가 일치하지 않는 경우다.

즉, 101111의 &연산의 결과는 010000이 된다.

구한 bit 결과에 위에서 계산한 결과에 일치시키기 위해 한자리 수 내리면 원하는 값을 얻을 수 있다.

// 홀수의 경우
// 올림을 해서 최소 2개의 비트가 바뀌게 해준다.
long long bit = 1;
while(true){
    if((x & bit) == 0)
        break;
    bit *= 2; // 곱하기 2를 통해 다음 비트로 이동
}
bit /= 2;
return x + bit;

 

비트를 굳이 올려놓고 다시 내리는 이유는 올림 연산을 위한 것이다.

만약 break된 bit 자리 수를 그대로 사용한 경우 1111111이 될 것이다.

이 경우는 원하는 1자리수만 바뀐 경우 이지만, 가장 작은 숫자는 아니다.

따라서 01 -> 10 올림 연산을 위해 1비트 내리는 것이다.

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

long long f(long long x){
    // 짝수의 경우 n + 1
    // 2 -> 3, 4 -> 5
    if(x % 2 == 0){
        return x + 1;
    }
    // 홀수의 경우
    // 올림을 해서 최소 2개의 비트가 바뀌게 해준다.
    long long bit = 1;
    while(true){
        if((x & bit) == 0)
            break;
        bit *= 2; // 곱하기 2를 통해 다음 비트로 이동
    }
    bit /= 2;
    return x + bit;
}

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    for(int i = 0;i<numbers.size();i++){
        long long x = numbers[i];
        answer.push_back(f(x));
    }
    return answer;
}