[NeetCode-LeetCode] Number of 1 Bits JAVA

반응형

728x90

[NeetCode-LeetCode] Number of 1 Bits - Easy

---

접근

• 비트 연산

---

풀이

주어진 정수를 2진수로 변환했을 때 해밍 웨이트를 구하는 문제이다. 해밍 웨이트(Hamming weight)는 2진수에서 0의 개수를 제외한 1의 개수라고 생각하면 된다. 예를 들어 n = 11 일 때 11은 2진수로 1011이고 1의 개수가 3개이므로 해밍 웨이트는 3이 된다. 

 

가장 간단하고 직관적인 방법으로 2진수로 변환을 한 뒤 직접 1의 개수를 세는 방법이다.

    public int hammingWeight(int n) {
        String binary = Integer.toBinaryString(n);
        
        int result = 0;

        for (char c : binary.toCharArray()) {
            if (c == '1') {
                result++;
            }
        }

        return result;
    }

기본적으로 자바에선 정수를 해당하는 진수 문자열로 변환을 제공하기에 간단하게 값을 얻을 수 있다. 물론 직접 2진수 변환 로직을 구성한다면 더 빠르거나 하겠지만 문제의 포인트는 아니므로 넘어간다. 그리고 변환 된 문자열에서 1의 개수를 세어 반환하면 된다.

직접 세기

역시나 정답은 아니다.

---

비트 연산

이 문제는 비트 연산 파트에 있었다. 비트를 직접 조작하여 문제를 풀어야 하는데 감이 잘 안잡혀 정답 코드를 봤다. 

    public int hammingWeight(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            if (((n >> i) & 1) == 1) {
                res += 1;
            }
        }
        return res;        
    }

>> 로 오른쪽 시프트 연산을 수행하는 코드였다. 정수형이 32비트이기 때문에 정수인 경우 모든 경우를 탐색하게 하였고 시프트 연산을 수행한 뒤 1과 and 연산으로 맨 마지막 오른쪽 한 자리만 남겨 검사하였다.

n = 1011

i = 1
n = 0101
n & 1 = 0101 & 0001 = 0001
if(n & 1 == 1) res++

i = 2
n = 0010
n & 1 = 0010 & 0001 = 0000
if(n & 1 != 1)

위와 같은 과정으로 결과를 구할 수 있었다.

---

전체 코드

직접 세는 방법

class Solution {
    public int hammingWeight(int n) {
        String binary = Integer.toBinaryString(n);
        
        int result = 0;

        for (char c : binary.toCharArray()) {
            if (c == '1') {
                result++;
            }
        }

        return result;
    }
}

 

비트 연산

public class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            if (((n >> i) & 1) == 1) {
                res += 1;
            }
        }
        return res;        
    }
}