꿀잠

https://leetcode.com/problems/sum-of-two-integers/description/

"+", "-" 없이 주어지 두 수의 합계를 구하는 문제이다. 비트 연산자를 이용하여 해결해야 한다.

십진수를 더할 때 자리수 별로 더하고 다음 자릿수로 넘겨서 더해주는 방식에 착안해서 해결해보았다. "^" 연산자를 사용해서 0과 1의 합계를 더해주고, "&" 연산자를 사용해서 1과 1의 합계 부분을 구한 이후 자릿수 올리기를 반복해주었다. 최종 코드는 아래와 같이 하여 통과하였다.

public class Solution {  
    public int getSum(int a, int b) {  
        while(b != 0){  
            int temp = a;  
            a = a ^ b;  
            b = b & temp;  
            b = b << 1;  
        }  
  
        return a;  
    }  
}

https://leetcode.com/problems/reverse-bits/description/

주어진 인트의 32비트 2진수 값을 순서를 반전 하였을 때 값을 리턴하는 문제이다.
StringBuilder 클래스의 reverse 메서드를 통해 문자열을 반전하기 쉬워 해당 메서드를 이용하여 해결하였다.

public class Solution {  
    public int reverseBits(int n) {  
        String from = Integer.toString(n, 2);  
        StringBuilder sb = new StringBuilder(from);  
        sb.reverse();  
  
        int needZero = 32 - sb.length();  
        for(int i = 0; i < needZero; i++){  
            sb.append('0');  
        }  
  
        return Integer.valueOf(sb.toString(), 2);  
    }  
}

비트 연산자를 이용해 해결하고 싶다면 아래와 같은 방식으로 해결할 수 있다.

class Solution {
    public int reverseBits(int n) {
        int result = 0;
        
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n >>>= 1;
        }
        
        return result;
    }
}

https://leetcode.com/problems/counting-bits/description/

bit의 개수를 새는 문제로 특정 숫자가 아니라 n까지의 모든 개수를 세는 문제이다. n이 충분히 크다면 속도가 굉장히 느려질 것을 예상해서 문제를 풀어야 할 것으로 추측할 수 있다. dp 방식으로 기존의 값에서 개수를 가져와야 빠르게 샐 수 있다. 이진수는 커질수록 자리수가 늘어난다는 점에서 착안하면 점화식을 세울 수 있다.

2, 3과 4의 이진수는 아래와 같다. 

2 - 10
3 - 101
4 - 100

3과 4는 2의 이진수에 1과 0이 추가된 형태이다. 2가 가진 1의 개수를 알 수 있다면 3의 경우 1개 추가된 것이고, 4의 경우 0개 추가되어 같은 것이다. 위와 같이 2와 3,4의 관계는 비트 이동 연산자를 통해 쉽게 찾을 수 있다. 3과 4의 비트를 오른쪽으로 한 칸 이동하면 되기 때문이다. 이와 같은 생각을 바탕으로 점화식을 세워 아래와 같이 풀 수 있다.

public class Solution {  
    public int[] countBits(int n) {  
        int[] ans = new int[n + 1];  
        for(int i = 0; i <=n; i++){  
            int cnt = 0;  
            ans[i] = ans[i >> 1] + (i & 1);  
        }  
  
        return ans;  
    }  
}

주어진 양수의 비트의 값이 1의 개수를 세는 문제이다. 최초 해결 후 비트연산자 학습을 위해 추가로 해결해보았으며 총 3가지 방법으로 해결해보았다.

1. 일단 주어진 자연수를 2진수로 변환하여 문자열에서 '1'의 개수를 세는 방법으로 해결하였다.
2. 하지만 비트 조작의 카테고리에 맞춰 풀기 위해 비트 이동 연산자와 '&' 논리 연산자를 이용하여 해결해보았다.
3. 관련해서 비트 연산자를 공부하던 중 Java 의 경우는 개수를 세어주는 Integer 메서드 bitCount 가 있다는 사실도 알았다. 해당 메서드를 이용해서도 바로 문제가 해결된다.

아래 코드는 세가지 모두 적어두었다.

public class Solution {  
    public int hammingWeight(int n) {  
    
        // 1. 문자열 이용  
        // String s = Integer.toString(n, 2);  
        // int answer = 0;        
        // for(char c: s.toCharArray()){        
        //     if(c == '1') answer++;        
        // }        
        // return answer; 
         
         
        // 2. 비트연산자 이용  
        // int answer = 0;  
        // while(n != 0){        
        //     if((n & 1) == 1) answer++;        
        //     n = n >> 1;        
        // }        
        // return answer;  
        
        
        // 3. Java Integer 메서드 이용  
        return Integer.bitCount(n);  
    }  
}

https://leetcode.com/problems/single-number/description/

비트 조작 문제이다. 비트 연산자는 잘 사용하지 않았지만, 기본적인 원리 정도는 이해하고 있었다.

해당 카테고리를 보고 비트 연산자를 복습한 이후 문제 풀이를 진행했다.

java에서는 &, |, ^, ~ 를 비트 논리 연산자로 사용할 수 있다. 비트를 이동 시키는 연산자도 있지만 해당 문제를 해결하기 위해선 비트 논리 연산자를 이해하면 된다.

& 의 경우 비트의 값이 모두 1일 경우 1을 반환한다.(AND)
| 의 경우 비트의 값 중 하나가 1일 경우 1을 반환한다.(OR)
^의 경우 비트의 값이 다를 경우(0, 1), (1, 0) 일 경우 1을 반환한다.(XOR)
~의 경우 비트의 값을 반대로 변환한다.(NOT)

해당 문제를 해결하기 위해선 XOR 연산자가 적절하였다. 개인적으로는 4가지 논리에서 가장 생소한 부분으로 느껴지기도 했지만 문제를 읽고서 해당 논리 연산자가 필요한 것을 알 수 있었다.

문제는 한 번 등장한 값을 반환하는 것이 목표이다.
기본 시작 값을 0으로 하여, 값들에 XOR 연산자를 더 할 경우 첫 번째 등장 시에는 비트에 값이 1로 새겨지며 더해지겠지만, 두번째 값이 등장 시 비트를 0으로 바꾸어 값을 지우게 된다. 최종적으로 한 번 등장한 값만 비트에 값을 새기며 정답의 2진수에 맞게 된다. 서로 다른 값이 같은 비트를 수정한다 하더라도 짝수 번 반복하여 값을 지우기 때문에 다른 값이 같은 비트를 수정하는 경우도 문제가 되지 않는다. 아래는 비트 논리 연산자를 사용하여 해당 문제를 해결한 코드이다.

public class Solution {  
    public int singleNumber(int[] nums) {  
        int answer = 0;  
  
        for(int num : nums){  
            answer = answer^num;  
        }  
  
        return answer;  
    }  
}