문제

풀이

당연히 $O(\log n)$으로 푸는건줄 알았음

class Solution {
public:
    int hammingWeight(int n) 
    {
        string s;
        while(n != 0)
        {
        	int t = n%2;
            n /= 2;
            if(t == 0) continue;
            s += "1";
        }
        
        return s.size();
    }
};

근데 이렇게 나오는거임...
이거 logn이 아니라
딱 상수 시간복잡도라는걸 느낌

그래서 고민해본결과 비트연산을 하면 된다는걸 깨달아버림

입력 변수 n을 오른쪽으로 한칸씩 땡기면서
그 수랑 1과 &연산을 했을때 1이면 count증가,
아니면 continue를 하면 된다는걸 찾아벌임

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

이러면 $O(1)$의 상수 타임에 가능해져버림