[PGM_77885] 2개 이하로 다른 비트 (Java)

문제링크

https://programmers.co.kr/learn/courses/30/lessons/77885?language=java 

코딩테스트 연습 - 2개 이하로 다른 비트

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 비트연산자

1. 문제 이해

$f(x)$ = $x$ 보다는 크지만 비트 2개만 변경된 값 중 최소값으로 정의되는 함수 $f$가 있을 때, $f(x)$의 값을 구해주는 문제이다. 

 

2. 접근방법

bit연산자인 &연산자를 사용하여 문제를 해결할 수 있다.

 

&연산자는 and연산으로 a & b에서 불 대수 a,b가 모두 1인 경우만 1이다.

비트 두개만 변경하여 최소가 되기 위해서는 가장 작은 위치의 0값을 찾아 1로 바꾸어주고 가장 작은 위치 바로 아래의 1을 0으로 바꾸어주는 경우가 최대이다.

 

즉 비트연산 10111011이 있는 경우 파란색으로 표시된 0이 최소자리의 0이므로 그 부분을 1로 변경하여주고, 그리고 바로 뒤 빨간색 1을 0으로 변경해주면 된다. 이 연산은 0100을 더해주고 0010을 빼주는 것과 같다.

 

예외적인 상황으로는 1111110와 같이 처음이 0인 경우이다. 이 경우는 빼줄 수 있는 경우가 없으므로 빼는 연산은 수행하지 않는다. 

구현코드

package pgm_77885;

public class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        int idx = 0;
        for(long number : numbers){
            long value = solve(number);
            answer[idx++] = value;
        }
        return answer;
    }

    public long solve(long number){
        long depth = 0;
        long target = number;
        while (true){
            if((target&1) == 0){
                break;
            }
            target /= 2;
            depth++;
        }

        double addValue = Math.pow(2, depth);
        double minusValue = depth == 0 ? 0 : Math.pow(2, depth-1);
        return number + (long) addValue - (long)minusValue;
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)