[LeetCode] 191. Number of 1 Bits

191. Number of 1 Bits

LeetCode

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).

양의 정수 n이 주어졌을 때, 해당 숫자의 이진수 표현에서 '설정된 비트(set bits, 값이 1인 비트)'의 개수를 반환하는 함수를 작성하세요 (이는 해밍 가중치(Hamming weight)라고도 부릅니다).

 

Example

Input: n = 11
Output: 3
Explanation:
The input binary string 1011 has a total of three set bits.

Input: n = 128
Output: 1
Explanation:
The input binary string 10000000 has a total of one set bit.

Input: n = 2147483645
Output: 30
Explanation:
The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

---

1. 문제 요구사항 분석

숫자를 이진수로 바꾼 다음, 1의 갯수 세기

 

Hamming weight (해밍 가중치)란
코딩 이론, 정보 이론 및 컴퓨터 과학에서 문자열(주로 이진수) 내에서 0이 아닌 기호의 개수

 

2. 접근 전략

십진수를 이진수로 바꾼 다음

😭 for문으로 1의 갯수 세기 → 시간복잡도 O(n)

😭 Integer.bitCount(n) 사용하기 → 시간복잡도 O(1) You are submitting too frequently.

(이 문구는 처음 나와서 신기했다.. !!!!!)

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

 

😄 브라이언 커니핸(Brian Kernighan) 알고리즘 사용하기

공부하면서 처음 알게 된 알고리즘인데, n = n & (n - 1)을 사용하는 것이다!!

 

브라이언 커니핸(Brian Kernighan) 알고리즘이란,
정수(이진수)에서 1로 설정된 비트(Set bits)의 개수를 효율적으로 세는 방법

 

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        
        // n이 0이 될 때까지 (즉, 1이 다 지워질 때까지)
        while (n != 0) {
            n = n & (n - 1); // 가장 오른쪽에 있는 1을 지워버림!
            count++;         // 지울 때마다 카운트 1 증가
        }
        
        return count;
    }
}

 

이렇게 하지 않아도

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        
        // n이 0이 아닐 때까지 반복 (음수도 처리 가능)
        while (n > 0){
        	// 맨 끝 비트가 1인지 확인
            if((n & 1) == 1){
                count++;
            }
            // 부호 상관없이 무조건 0을 채우며 오른쪽으로 밀기!
            n = n >>> 1;
        }
        return count;
    }
}

 

비트 공부는 좀 더 해야겠다.... 어렵다...