프로그래머스 2개이하로다른비트 c++ // 비트마스킹, 관찰, 규칙성발견

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

프로그래머스

1. 관찰, 규칙성발견

1. 완탐 -> 너무 빡구현 & 10^15 -> 불가능

2. 관찰을 통한 규칙성발견

1(1)
2(10)

2(10)
3(11)

3(11)
5(101)

4(100)
5(101)

5(101)
6(110)

6(110)
7(111)

에서 

최초0을찾고 // num and i ==false -> 최초0의 위치

그곳을 1로바꾸고 // *or1 -> 무조건 1이됨

이전비트를 0으로 바꾸면 된다. // 1 xor 1 -> 무조건 0이됨.

 

2. 전체코드

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for(auto number : numbers){
        for(ll i=1;;i=i<<1){ //i : 00001, 00010 ...
            if((number & i)==0){ //0을만나면 (== 직전비트는 1이었음)
                number=number|i; //현재비트를 1로바꾸기
                number=number^(i>>1); //이전비트(1확정)를 0으로 바꾸기 (1^1==0 임)
                answer.push_back(number);
                //cout<<number<<" ";
                break;
            }
        }
    }
    return answer;
}