아찌방 하우스

https://fall-in-dream.tistory.com/86

위의 글을 보신 분들 중

의아한?궁금한? 부분이 있으신 분들이 있을거라고 생각합니다.

그것은 바로

1. NOT 연산의 결과

2. >>연산과 >>>의 차이

라고 생각합니다.

이번에는 우선 NOT 연산의 결과를 다시 한 번 살펴 봅시다.

int a = 5(0101) 를

Not 연산 결과로

-6(1010)이 나왔습니다.

'0101'을 NOT(~) 연산했으니 0과 1이 반대가 돼서 '1010'이 나온 것까지는 OK

근데 '1010'은 12가 아닌가?

생각할 수 있습니다.

NOT연산자를 이해하기 위해서는

JAVA는 2의 보수를 사용하는 것을 알아야 합니다.

예로,

int 형의 변수는 32비트로 나타내는데

즉, int a = 5; 라고 하면

우리가 보기에는 '0101'이지만

사실은

'0000  0000  0000  0000  0000  0000   0000  0101'이라는 사실!!!!

그러면 이 것을 NOT(~) 연산한다면?

'0000  0000  0000  0000  0000  0000   0000  1010'이 아니라

'1111  1111  1111  1111  1111  1111   1111  1010'가 되는 겁니다!!!!

이진수 '1111  1111  1111  1111  1111  1111   1111  1010' 는 부호 비트가 1로 시작하므로 음수로 간주됩니다.

이진수에서 2의 보수를 취하면 해당 음수의 양수 표현이 됩니다.

따라서 '1111 1111 1111 1111 1111 1111 1111 1010'의

2의 보수는

'0000 0000 0000 0000 0000 0000 0000 0110'이 되고, 이는 10진수로 -6입니다.

(2의 보수에 대해서는 다음에 한 번 다루어 보도록 하겠습니다.)

그러면 다음에는

>>연산과 >>>연산의 차이에 대해 들고 오겠습니다!!!

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

풀이 - 나의 생각

처음에는

주어진 숫자(numbers[i])에 +1(이하 B)을 하고

XOR 연산을 한 후

Long.bitCount 를 통해 1의 갯수의 차이를 구한다.

이 차이가 2이하일 경우 answer[i]에 값을 저장한다.

아닐 시 B에 +1을 한다.

위를 반복했다.

결과적으로 시간 초과가 발생했다.

아무래도 숫자가 커질 수록 (주어진 범위가 10의 15승이다)

비트 1개의 차이를 찾는게 오래 걸리는 것이라고 판단했다.

그래서 단순하게 생각했다.

그냥 2진법을 생각하면

맨 오른쪽부터 1, 2, 4, 8, 16, ........ 2의 n배 수를 나타낸다.

그러면 그 숫자들을 더한다.

더해서 나온 수와 numbers[i] 값을 XOR 연산 후

1의 개수를 세어본다.

그게 2 이하면 정답이라는 것이다.

코드

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        long a = 0, plus = 1;
        long tmp = 0;
        for(int i = 0; i <numbers.length; i++){
            a = numbers[i];
            plus = 1;
            String num = Long.toBinaryString(a);
            for(int j = 0; j < num.length(); j++){
                tmp = Long.bitCount(a ^ (a + plus));
                if(tmp <= 2) {
                    answer[i] = a + plus;
                    break;
                }
                plus *= 2;
            }
        }
        return answer;
    }
}