꿀잠

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;  
    }  
}