개발자 Lim

조건:

• 1 <= num < 231

의역: 정수의 complement는 이진 표현에서 0을 1로 1을 0으로 뒤집을 때 얻을 수 있는 정수 입니다.

ex: 5 -> 101 (이진법 표시) 뒤집는다면 010 -> 2

정수 하나가 주어질 때 해당 정수의 complement를 반환하시오  

+ 이진법 이란? 2의 제곱수로 각 자리수를 표현한 것 현재 실생활에서 일반적으로 쓰고 있는 숫자 체계는 10진법 

ex (이진법): 2^2 x 3 + 2^1 x 3 + 2^0 x 3 = 12 + 6 + 3 = 21

(10진법): 10^1 x 2 + 10^0 x 1 = 20 + 1 = 21 

5 = 101 (이진법 표시)  reverse -> (010) = 2 따라서 2를 반환

1 = 1 (이진법 표시) reverse -> 0 = 0 따라서 0을 반환 

풀이: 

1. ^ xor 연산자이용 (서로 다른 비트값이면 1 같다면 0 리턴) 

class Solution {
    // 해당 값의 비트 자리수의 최대 값이 될 수 있는 경우를 반환
    private int getMaxBitValue(int n){
        int i = 0;
        int max = 0;
        // 비트 자리수 계산
        // i = (int) Math.floor((Math.log(n) / Math.log(2)) + 1); 대체 가능
        while(n!=0){
            n/=2;
            i++;
        }
        // 해당 비트 자리수의 최대 값 구하기
        // max = (1 << i) - 1; 대체 가능
        for(int bit=i-1;bit>=0;bit--){
            max+=Math.pow(2,bit);
        }
        return max;
    }
    public int findComplement(int num) {
		// ex 5  5(101)^(111) -> (010)
        return num^getMaxBitValue(num);
    }
}

2. & 연산자와 Integer.highestOneBit(int num) 함수 이용

Integer.highestOneBit(int num) 함수는 해당 정수의 제일 왼쪽의 bit 값의 정보를 반환한다

ex Integer.highestOneBit(5) = 4  

class Solution {
    public int findComplement2(int num) {
    // ex:  5(101) ~5(010) & 4-1(011) = 2(010)
        return ~num & (Integer.highestOneBit(num)-1);
    }
}

링크: https://leetcode.com/problems/number-complement/