(Binary, Easy) Number of 1 Bits

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

참고: Integer 클래스에는 bitCount라는 메서드가 존재한다.

솔루션 참고해보니 -1 값과 함께 AND연산해가며 카운트하는 방식이 있고
아니면 int가 32비트라는 점을 참고해서 32번의 shift와 AND연산하며 카운팅하는 방식이 있다.

두 방법은 모두 O(1)로 표기할 수 있다.

방법1.
10진으로 -1이라면 2진으로 당연히 마지막 비트만 하나 까기 때문에 AND연산을 해서 다시 넣으면 뒤에서부터 하나씩 1 비트를 지워가는 셈이 된다.

결국 루프를 계속 돌다 보면 00000... 으로 채워지게 되는데 이것으로 종료 시점을 알 수 있다.
while (n > 0)

class Solution {
    public int hammingWeight(int n) {
        int cnt = 0;
        while (n > 0) {
            n = n & (n-1);
            cnt++;
        }
        return cnt;
    }
}

방법2
int는 32비트이므로 32번만큼 순회하며 i값을 증가시키며 시프트시켜본다.
1만큼 shift, 2만큼 shift, 3만큼 shift ....

시프트한 결과에 1로 AND연산을 한 결과가 1이면 채워진 비트로 볼 수 있다.
따라서 오른쪽 끝에서부터 하나씩 당겨가며 끝자리가 1 비트냐고 묻는 것과 같다.

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