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

// f(x) x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수
// 1 <= numbers.length <= 100,000
// 0 <= numbers <= 10^15

// 비트연산을 하나씩 빼서 짝수가 될때까지 빼기 -> x값 구하기
// 답 : 2 ^ (x - 1)

class Solution {
    public long[] solution(long[] numbers) {
        int length = numbers.length;
        long[] answer = new long[length];
        for(int i = 0; i < length; i++){
            long num = numbers[i];
            long x = 0;
            if(num % 2 == 0)
                x++;
            while(num % 2 == 1){
                num = num >> 1;
                x++;
            }
            answer[i] = numbers[i] + (long)Math.pow(2, x-1);
        }
        return answer;
    }
}

처음에 어떠한 경우에 3개 이상 다른 것이 생겨나는지 파악하면 쉽다.

1이 연속된 비트로 끝날 경우 발생하므로, >> 연산을 통해 1의 갯수(x)를 구하고 2^(x-1)을 해주면된다. 단 0인경우는 답이 다르게나오니 처리해줘야한다.