[Java] 비트 연산

프로그래머스

 

⛅️ Intro

프로그래머스에 비트 연산을 사용해야 하는 알고리즘 문제를 경험했다. 평소에 진수 변환만 사용하다가 더 다양한 풀이에 접목시키고자 학습한 내용을 정리하고 공유한다!

 

Java 에서의 진수 변환

비트 연산에 대해 설명하기 이전에 진수를 변환하는 방법에 대해 먼저 공유한다.

 

1. Integer.toString(i, radix)

Integer.toString(7, 2);

[Result] : 111

 

Integer.toString()

 

Integer.toString() 메서드의 첫번째 파라미터인 i에  진수변환할 수를 입력하고, 두번째 파라미터인 radix 진수를 입력한다.

return Type 은 String 임에 주의하자.

 

2. Integer.toBinaryString(i)

Integer.toBinaryString(7);

[Result] : 111

 

Integer.toBinaryString()

 

Integer.toBinaryString() 메서드의 첫번째 파라미터인 i에  진수변환할 수를 입력한다. return Type 은 Integer.toString과 동일한 String 이다.

 

위의 두 메서드는 알고리즘 풀이를 할 때 유용하게 사용했던 기억이 있어 잊지 않게 복기했다.

 

Java 에서의 비트 연산, 문제 풀이에 적용해보기

비트 연산을 프로그래머스 문제의 풀이에 접목한 예시를 통해 설명해 보겠다. 요구사항 상황은 아래와 같다.

 

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

 

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

 

위의 정의를 통해 `x` 와 1~2개 비트가 다른 가장 작은 수를 찾기 위해 다음과 같은 접근을 할 수 있다.

 

1. x가 짝수인 경우

가장 낮은 비트(Least Significant Bit, LSB) 가 0 이다. (8 : 1000, 4 : 100, 2: 10 등) 이 경우, `x`와 비트가 1개만 다른 수는 단순히 `x+1`이 된다. 가장 낮은 비트를 1로 바꾸면 그것이 `x`보다 크고 비트가 단 1개만 다른 가장 작은 수가 되기 때문이다.

 

2. x가 홀수인 경우

가장 낮은 비트가 1이다. 이 경우, `x`와 비트가 1개 다른 수를 찾으려면 가장 낮은 0비트를 1로 변경하고, 변경한 1 오른쪽에 있는 1을 0으로 변경해야 한다. 

 

이 2가지 케이스를 코드로 풀이 해보자!

 

1. x가 짝수인 경우

if (x % 2 == 0) {
    // 짝수인 경우, 1을 더함
    answer[i] = x + 1;
}

 

위에서 설명한대로 `x`에 1만 더해주면 된다.

 

2. x가 홀수인 경우

// 홀수인 경우
// 가장 낮은 0 비트를 찾아서 1로 만들고, 그 바로 오른쪽 비트를 0으로 만듦
if(x % 2 != 0){
    // 가장 낮은 0 비트 위치를 찾음
    long rightmostZero = ~x & (x + 1); 
    // 가장 낮은 1 비트 위치를 찾음
    long rightmostOne = rightmostZero >> 1;
    
    return x + rightmostZero - rightmostOne;
}

 

와 같이 코드를 작성할 수 있다. 이에 대해 자세히 설명한다.

 

2.1 가장 낮은 0 비트의 위치 찾기

// 가장 낮은 0 비트 위치를 찾음
long rightmostZero = ~x & (x + 1);

 

x 가 7인 경우를 예시로 들어보자. 우선 '~x' 연산은 `x`의 모든 비트를 반전시킨다. 즉 0은 1로, 1은 0으로 바뀐다.  x = 7 (0111 이진 표현)의 반전은 1000임을 확인할 수 있다.

`x+1` 연산은 `x`가 홀수이므로, 이 연산은 가장 낮은 비트(LSB) 에서 올림이 발생하게 만들고, 그 결과 `x`의 가장 낮은 0 비트가 1로 바뀐다.

즉, `~x & (x+1)` 연산은 ~x 와 x+1 의 AND 연산을 통해 x의 가장 낮은 0 비트의 위치에 해당하는 비트만 1로 설정된다. 이를 통해 가장 낮은 0 비트를 찾을 수 있다. (1000 & 1000 = 1000) 4번째 비트가 1로 설정된다.

 

2.2 가장 낮은 1비트 위치 조정

// 가장 낮은 1 비트 위치를 찾음
long rightmostOne = rightmostZero >> 1;

 

[2.1] 을 통해 가장 낮은 0 비트의 위치를 찾았다. 다음으로 가장 낮은 1의 비트 위치를 조정한다. 홀수 정수에서 rightmostZero 바로 오른쪽에 있는 비트 항상 1이다. 그것이 가장 낮은 0비트의 위치를 정의하기 때문이다.  rightmostZero (1000)를 오른쪽으로 1비트 시프트하면 0100이 된다. 이는 `x`의 가장 낮은 0비트 바로 오른쪽에 있는 1비트의 위치를 나타낸다.

 

2.3 최종수 계산

long x = 7;

/*
 7 : 0111
~7 : 1000
 8 : 1000
*/

// ~7&8 : 1000 (8)
long rightmostZero = ~x & (x + 1);

// 1000 >> 1 : 0100 (4)
long rightmostOne = rightmostZero >> 1;

// 7+8-4 : 11
answer[i] = x + rightmostZero - rightmostOne;

 

즉, 주어진 수 x 에 가장 낮은 0의 자리인 rightmostZero 를 1로 바꿔주고 (+rightmostZero), 가장 낮은 0 비트 바로 오른쪽의 1을 0으로 만들어준다.(-rightmostOne) 이는 이진수로 11에 해당한다.

 

이러한 과정을 통해서 값을 도출할 수 있다. 전체 코드는 아래와 같다.

 

import java.util.*;

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        
        for (int i = 0; i < numbers.length; i++) {
            long x = numbers[i];
            if (x % 2 == 0) {
                // 짝수인 경우, 1을 더함
                answer[i] = x + 1;
            } else {
                // 홀수인 경우
                long rightmostZero = ~x & (x + 1);
                long rightmostOne = rightmostZero >> 1;
                answer[i] = x + rightmostZero - rightmostOne;
            }
        }
        
        return answer;
    }
}