LeetCode 191 — Number of 1 Bits (이진수에서 1 개수 세기)

📝 LeetCode 191 — Number of 1 Bits

두 가지 풀이 비교 (Brian Kernighan vs 32-bit Loop)

https://leetcode.com/problems/number-of-1-bits/description/

 

 

비트 연산 문제에서 가장 자주 등장하는 문제 중 하나가 191. Number of 1 Bits다.
정수의 이진 표현에서 1의 개수를 세는 문제로 단순해 보이지만,
풀이 방식에 따라 효율성과 구현 난이도가 크게 달라진다.

이 글에서는 가장 통상적으로 쓰이는 두 가지 방법을 비교해 본다.

---

1. 문제 설명 (요약)

주어진 정수 n의 이진수 표현에서 1 비트의 개수(Hamming Weight) 를 구하라.

• 입력은 32비트 unsigned integer 로 처리해야 한다.
• 예시
•  
  n = 00000000000000000000000000001011 output = 3

---

2. 풀이 1 — 32비트 전체 순회 방식 (Brute-force but Standard)

가장 직관적이면서도 초보자가 바로 떠올릴 수 있는 풀이이다.
n의 모든 비트(0~31)를 확인하여 1인지 검사한다.

✔ 핵심 아이디어

• AND 연산 (n & 1)으로 마지막 비트가 1인지 확인
• 한 칸씩 오른쪽 시프트 n >>= 1
• 총 32번 반복

✔ 코드

public int HammingWeight(int n)
{
    int count = 0;
    for (int i = 0; i < 32; i++)
    {
        count += (int)(n & 1);
        n >>= 1;
    }
    return count;
}

 

✔ 장점

• 직관적이고 이해하기 쉬움
• 비트 연산 기본기를 익히기 좋음
• 모든 언어에서 동일한 방식으로 적용 가능

✔ 단점

• 항상 32번 반복해야 함
• n에 1이 몇 개 있는지 상관없이 동일한 시간 소요 (O(32) = O(1))

---

3. 풀이 2 — Brian Kernighan 알고리즘

가장 오른쪽에 있는 1비트를 제거하며 반복하는 방식이다.

✔ 핵심 아이디어

Brain Kerninghna Algorithm

n & (n - 1) 을 하면
👉 n에서 가장 오른쪽에 있는 1이 제거된다.

즉, 1이 3개이면 3번, 1이 10개이면 10번만 루프를 돈다.

✔ 코드

 

public int HammingWeight(int n)
{
    int count = 0;
    while (n != 0)
    {
        n &= (n - 1);
        count++;
    }
    return count;
}

✔ 장점

• 불필요한 비트 검사를 하지 않음
• 1의 개수만큼 루프 → 훨씬 빠름
• 비트 최적화 테크닉으로 매우 유명
• 면접에서 높은 평가

✔ 단점

• 처음 보면 원리가 이해되기 어려움
• 비트 구조를 모르면 외우기만 할 가능성 있음

 

 

비트 연산 문제에 자주 등장하므로 반드시 두 방식 모두 이해해두면 좋다.