leetcode - 476. Number Complement

The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.

• For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.

Given an integer num, return its complement.

 

Example 1:

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

 

문제 : int num이 파라미터로 주어지는데, 해당 num 을 이진수로 변경하고, 0과 1일 반전시켜라

 

1) 나의풀이

class Solution {
    public int findComplement(int num) {
        int bitLen = Integer.toBinaryString(num).length(); 
		int nNum = ~num;
		
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<bitLen;i++) {
			sb.append(nNum&1);
			nNum = nNum>>1;
		}
		
		return Integer.parseInt(sb.reverse().toString(), 2);
    }
}

 

풀이 : num 의 length를 구한다. 주어진 num의 비트연산 ~을 한다.

        만약 num =5 이면,

        00000000000000000000000000000101 5를 이진수로 표현

        11111111111111111111111111111111 ~5를 이진수로 표현
        필요로하는값은 맨뒤 3개이다. 3개값을 int로 변환후 반환한다.

 

 

2) leetcode 풀이

class Solution {
    public int findComplement(int num) {
		int mask = -1;
		while ((num & mask) != 0) {
			mask <<= 1;
		}
		
		return ~(num ^ mask); //~num & ~mask
    }
}

 

 

풀이 : 

      만약 num=5 라면
      00000000000000000000000000000101 num(5)를 이진수로 표현
      11111111111111111111111111111111 mask(-1) 2진수로 표현 
      11111111111111111111111111111110 mask<<1 1회차
      11111111111111111111111111111100 mask<<1 2회차
      11111111111111111111111111111000 mask<<1 3회차
     

      num&mask == 0 일때까지 while 문을 돈다.

      이로써, num의 leading zero가 어디까지인지 알수있다.

   
              00000000000000000000000000000101
              &(두 비트 모두 1일 경우에만 연산 결과가 1)
              11111111111111111111111111111000 (뒤에 3개를 제외하고는 나머진 리딩제로)
   > 결과 : 00000000000000000000000000000000
    

 

      num^mask 연산을 통해서, 앞에 leading zero에 1값으로 채워준다.

               00000000000000000000000000000101
               ^(두 비트중 하나는 1이고 다른 하나가 0일경우에만 연산결과가 1 즉, 둘이 다르면 1 아니면 0)
               11111111111111111111111111111000
    > 결과 : 11111111111111111111111111111101
    

   
        답 : ~(num^mask)

              11111111111111111111111111111101 를 ~비트연산을 진행하면

              00000000000000000000000000000010이 된다.