Level 2. 2개 이하로 다른 비트

Level 2. 2개 이하로 다른 비트

 

 

num부터 1씩 증가시키면서 비트셋과 XOR 연산을 이용해 다른 비트의 개수를 찾는 풀이이다.

 

하지만, 이 풀이는 시간 초과가 발생한다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>

using namespace std;

vector<long long> solution(vector<long long> numbers)
{
    auto func = [](long long num)
    {
        int diff = 0;
        bitset<64> bset(num);

        while (diff != 1 && diff != 2)
            diff = (bset ^ bitset<64>(++num)).count();

        return num;
    };

    transform(numbers.begin(), numbers.end(), numbers.begin(), func);

    return numbers;
}

 

반복 없이 바로 정답을 찾는 풀이다.

 

마지막 비트가 0이면 바로 1만 증가시키면 되고, 그렇지 않다면 next_permutation() 함수를 통해 다음으로 가장 작은 수를 찾는다.

• next_permutation() 함수를 실행하면 항상 2개의 비트가 바뀐다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>

using namespace std;

vector<long long> solution(vector<long long> numbers)
{
    auto func = [](unsigned long long num)
    {
        if (~num & 1)
            return ++num;

        string s = bitset<64>(num).to_string();
        vector<char> v(s.begin(), s.end());

        next_permutation(v.begin(), v.end());

        return bitset<64>(string(v.begin(), v.end())).to_ullong();
    };

    transform(numbers.begin(), numbers.end(), numbers.begin(), func);

    return numbers;
}

 

LS0는 Least significant 0의 줄임말로 쓴 것이며, 가장 우측에 있는 0의 위치를 나타낸다.

 

가장 우측에 있는 0을 1로 바꾸고 그 오른쪽 비트를 0으로 바꾸는 풀이다.

• 11101 -> 11110
• 11100 -> 11101

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<long long> solution(vector<long long> numbers)
{
    auto func = [](long long num)
    {
        long long LS0 = (~num & -~num);

        return num + LS0 - (LS0 >> 1);
    };

    transform(numbers.begin(), numbers.end(), numbers.begin(), func);

    return numbers;
}

 

아래는 가장 우측의 0을 반복문을 통해 찾는 일반적인 방법이다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<long long> solution(vector<long long> numbers)
{
    auto func = [](long long num)
    {
        long long LS0 = 1;

        while (num & LS0)
            LS0 <<= 1;

        return num + LS0 - (LS0 >> 1);
    };

    transform(numbers.begin(), numbers.end(), numbers.begin(), func);

    return numbers;
}