[leetcode]191. Number of 1 Bits

문제:
n이 주어졌을 때,
2진법으로 표현했을 때, 1의 개수를 리턴하기.

풀이1. 나머지와 몫을 이용한 개수 구하기

/**
 * @param {number} n
 * @return {number}
 */
var hammingWeight = function(n) {
    let remain = n;
    let count = 0;
    while(remain){
       if(remain == 2 || remain ==1 ){
            count +=1;
            break;
       }
        if(remain %2 == 1){
            count +=1
        }
        remain = Math.floor(remain /2)
    }
    return count;
};

2진법을 구할때, 나머지가 1일때마다 count++ 해주고,
마지막에 2나 1이 남으면 count ++ 하고 break 해주면 된다.

입력 값을 반으로 나누기 때문에 시간 복잡도는 O(log n)
공간복잡도 O(1)

다른 방법도 존재한다.

풀이2. 비트 연산자

n의 맨 오른쪽 비트가 1인지 확인하고, 오른쪽으로 한칸 밀어서 다음 비트를 검사하는 방법.

n=13이라고 할때,
n&1 => 결과는 마지막 비트가 나온다.
n = n>>>1 이 연산을 통해 오른쪽으로 1칸 shift를 한다.

let count = 0;
while (n !== 0) {
  count += n & 1;  // 마지막 비트가 1이면 count++
  n = n >>> 1;     // 오른쪽으로 한 칸 밀기 (비트 이동)
}

시간 복잡도 O(log n)
공간복잡도 O(1)

풀이 3. 비트마스킹 방식

let count = 0;
let mask = 1;
for (let i = 0; i < 32; i++) {
  if ((n & mask) !== 0) count++;
  mask = mask << 1;  // 왼쪽으로 한 칸 이동
}

mask는 한 자리씩 1인 비트를 왼쪽으로 옮기며
n과 & 연산을 해서 해당 위치가 1인지 아닌지를 확인하는 방법.
아직 이해를 못했다..ㅎㅎ

시간 복잡도 O(1) (하지만 O(logn)보다 좋다고는 못함)
공간복잡도 O(1)

풀이 4. n의 이진수에서 가장 오른쪽 1비트를 하나씩 제거하여 1의 개수를 세는 방법

/**
 * @param {number} n
 * @return {number}
 */
var hammingWeight = function(n) {
    let count = 0;
    while (n !== 0) {
        n = n & (n - 1);
        count++;
    }
    return count
};

/*

/
시간복잡도: O(k) : 여기서 k는 n에 포함된 1의 개수
공간복잡도: O(1)
/

참고자료:
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Operators/Unsigned_right_shift_assignment
https://travelbeeee.tistory.com/451