[LeetCode] #191 - Number of 1 Bits [Java][C++][Python]

문제 링크

---

1. 아이디어

양의 정수 n에 대해 2진수로 표현했을 때, 1인 비트의 수를 세는 문제다. 1인 비트의 수는 2진수로 표현했을 때 끝자리 비트가 1이면 세고 비트 시프트로 오른쪽으로 한 칸 미는 과정을 반복하면 간단하게 셀 수 있다. 또는 내장 함수를 활용해도 된다.

Follow up은 최적화를 언급하고 있는데 기본적인 방식들도 이미 매우 빨라서 큰 의미는 없다. 1바이트의 숫자에 대한 모든 1의 개수를 구한 룩업 테이블을 만든 후 n의 각 바이트별로 세는 방식을 활용할 수도 있고, Brian Kernighan’s Algorithm을 활용하면 효율적으로 1인 비트만 셀 수 있다.

---

2. 복잡도

접근	시간	공간
비트 시프트	$O(1)$	$O(1)$
표준 라이브러리	$O(1)$	$O(1)$
브라이언 커니핸 알고리즘	$O(1)$	$O(1)$

(n이 최대 $2^{31} - 1$인 32비트 정수로 고정돼 세 접근 모두 반복 횟수가 최대 32회를 넘지 않으므로 입력 크기와 무관하게 시간 $O(1)$)

---

3. 코드

풀이 1: 비트 시프트 [Java][C++][Python]

class Solution {
    public int hammingWeight(int n) {
        int cnt = 0;
        while (n > 0) {
            if ((n & 1) == 1) cnt++;
            n >>= 1;
        }

        return cnt;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
    int hammingWeight(int n) {
        int cnt = 0;
        while (n) {
            if (n & 1) cnt++;
            n >>= 1;
        }

        return cnt;
    }
};

class Solution:
    def hammingWeight(self, n: int) -> int:
        cnt = 0
        while n:
            if n & 1:
                cnt += 1
            n >>= 1

        return cnt

---

풀이 2: 표준 라이브러리 [Java][C++][Python]

class Solution {
    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
    int hammingWeight(int n) {
        return popcount((unsigned)n);
    }
};

class Solution:
    def hammingWeight(self, n: int) -> int:
        return n.bit_count()

---

풀이 3: 브라이언 커니핸 알고리즘 [Java][C++][Python]

class Solution {
    public int hammingWeight(int n) {
        int cnt = 0;
        while (n > 0) {
            n &= (n - 1);
            cnt++;
        }

        return cnt;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
    int hammingWeight(int n) {
        int cnt = 0;
        while (n) {
            n &= (n - 1);
            cnt++;
        }

        return cnt;
    }
};

class Solution:
    def hammingWeight(self, n: int) -> int:
        cnt = 0
        while n:
            n &= n - 1
            cnt += 1

        return cnt

---