[LeetCode] - 191. Number of 1 Bits

 

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Number of 1 Bits" 문제입니다.

 

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

문제:

Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).

---

Example 1:

Input : n = 11

Output : 3

Explanation : The input binary string 1011 has a total of three set bits.

 

Example 2 :

Input : n = 128

Output : 1

Explanation : The input binary string 10000000 has a total of one set bit.

 

Example 3 :

Input : n = 2147483645

Output : 30

Explanation : The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

 

Constraints : \(1 \leq n \leq 2^{31} - 1\)

---

한국어로 간단히 설명하자면, 이 문제는 양의 정수의 이진 표현을 받아 그 안에 1로 설정된 비트의 개수를 반환하는 함수를 작성하라고 요구합니다. 저는 우선 자바로 이 문제를 접근했으며, 풀이를 보여드리겠습니다:

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

// 또는 

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            // Check if the least significant bit is 1
            count += n & 1;
            // Shift n to the right to process the next bit
            n >>>= 1;
        }
        return count;
    }
}

 

위와 같이, 우선 int가 32 비트라는 것을 인지하고, for 루프를 통해 32번 반복합니다. 그 안에서는 매번 n을 오른쪽으로 i만큼 이동시킨 후, 최하위 비트가 1인지 확인합니다. 1이면 count를 증가시킵니다. 최종적으로 count 변수에는 n의 1로 설정된 비트의 개수가 저장되어 반환됩니다.

또는, 두번째 코드처럼 해도 됩니다 ; int가 32 비트라는 것을 인지하고, while 루프를 돌려 n이 0이 될 때까지 계속 진행합니다. 그 안에서는 매번 n의 최하위 비트가 1인지 확인하고, 1이면 count를 증가시킵니다. 그러고 나서, 다음 비트를 처리하기 위해 n을 오른쪽으로 이동시킵니다. 그러다 보면 count 변수에는 n의 1로 설정된 비트의 개수가 저장되어 리턴합니다.

왼쪽에서 순서대로 1,2번째 코드 Runtime