[LeetCode] 191. Number of 1 Bits (aka. Hamming Weight)

 바쁜 업무에 시달리다보니 LeetCode라는 알고리즘 공부하는 웹싸이트가 있다는걸 이제야 알게되었다. 육아도 바쁘고 나이가 들어서 몸이 좀 힘들지만 매일 최소 한 문제씩 풀어보기로 결심하고 어제부터 시작했는데 블로그에 글 까지 올리기에는 시간이 좀 빡빡하지만 하나 씩 올릴 생각이다.

 

 나는 LeedCode 초심자이니 당연히 Easy 레벨부터 시작!

 

191. Number of 1 Bits 문제는 주어진 4bytes(32bits) 정수에서 비트가 1인 비트의 개수를 카운트 하는 문제이다.

 

일단 C#으로 풀었다. C++ 코드도 별 차이가 없으나 귀찮으니 그냥 C#으로만...

public class Solution {
    public int HammingWeight(uint n) {
        var size = sizeof(uint) * 8; // 입력 변수가 몇 비트인지 계산
        uint result = 0;
        uint val = n;
        for (int i = 0; i < size; i++) // 단순하게 비트 수 만큼 반복한다
        {
            val = n >> i; // 입력 값을 i 만큼 우측으로 쉬프트 한다
            result += (val & 0x1); // 0x1로 AND 연산. 마지막 비트가 1이면 1, 아님 0
        }

        return (int)result; // 결과를 반환한다.
    }
}

 

난 일단 이렇게 풀었는데 최적 솔루션은 시간이 나면 한 번 들여다 봐야겠다. 비트 수 만큼 루프를 돌지 않고 해결하는 방법이 있을테니...