[LeetCode] 191. Number of 1 Bits

출처: leetcode.com/problems/number-of-1-bits/

Number of 1 Bits - LeetCode

문제

부호 없는 정수를 입력받아서 '1'비트의 수를 반환하라(Hamming weight를 계산하라).

예제

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

풀이

이 문제의 입력이 부호 없는 정수이기 때문에 입력으로 주어지는 값을 모두 양수로 취급해서 계산하면 된다. 주어진 정수의 1비트의 수를 계산하기 위한 방법으로 여러 가지가 있겠지만, 비트 연산자를 이용해서 계산하는 방식을 채택하였다.

 

& 연산을 이용하여 주어진 값과 1과 연산을 수행하면 마지막 자리의 숫자가 1인지 아닌지 판단할 수 있다.

입력 n = 7 이라면,
7 = 00000111
7 & 1 = 0000111 & 00000001 = 1

입력 n = 6 이라면,
6 = 00000110
6 & 1 = 00000110 & 00000001 = 0

이후, 주어진 입력을 오른쪽으로 쉬프트하면서 & 연산을 반복하면 되는데, >> 이 아닌 >>> 을 사용해야 한다. 그 이유는 >>을 사용하게 되면 쉬프트 연산을 통해 추가되는 최상위 비트가 기존 최상위 비트를 따르기 때문에 원하는 결과를 얻지 못할 가능성이 있다, 이에 >>>를 사용해서 쉬프트로 인해 추가되는 최상위 비트가 0이 되도록 하는 것이다.

- '>>' 연산
101101 >> 2 : 111011
011000 >> 1 : 001100

- '>>>' 연산
101101 >> 2 : 001011
011000 >> 1 : 001100

최종적으로 만들어지는 코드는 다음과 같다.

// JavaScript

function solution(n) {
    let answer = 0;
    while(n) {
        answer += n & 1;
        n = n >>> 1;
    }
    return answer;
}

또다른 풀이법으로는 주어지는 정수를 문자열로 변환해서 푸는 방법이 있다. 문자열에서 1을 찾는 방법도 다양하다. 반복문을 통해 1의 수를 직접 카운팅 할 수도 있고 정규표현식을 이용해서 찾을 수도 있다. 다음 코드는 정규표현식을 이용해서 코드 한 줄로 문제를 해결하는 코드이다.

// JavaScript

function solution(n) {
    return n.toString(2).match(/1/g)?.length ?? 0;
}

위 코드를 소개하는 이유는 문자열로의 변환을 통해 문제를 해결할 수 있다는 것을 보여주기 위함도 있지만, 가장 큰 이유는 ?., ??와 같은 익숙하지 않은 JavaScript 문법이 있기 때문이다. 두 문법 모두 ES2020에서 추가된 문법으로 간략히 어떤 문법인지 설명하면 다음과 같다.

• Optional Chaning: ?.
  • 객체를 명시적으로 검증하지 않고 속성에 안전하게 접근하는 문법, .과 유사하게 작동
  • .과 무엇이 다른가?
    • .의 경우, 접근하려는 객체가 null(혹은 undefined)일 경우 에러를 내뿜는다.
    • ?.의 경우, 접근하려는 객체가 null(혹은 undefined)일 경우 에러 없이 undefined를 반환한다.
• Nullish Coalescing operator: ??
  • 왼쪽 표현식 값이 null 또는 undefined일 때, 오른쪽 표현식 결과를 반환
  • ||과 무엇이 다른가?
    • ||의 경우, 왼쪽이 falsy(0, '', NaN, null, undefined)한 값일 때 오른쪽 표현식 결과를 반환하는 특성이 있다. 이 때문에 숫자 0을 false로 판단 내려 의도치 않은 결과를 만들기도 한다('', NaN 또한 마찬가지).
    • 하지만, ??의 경우에는 null과 undefined만을 취급하기 때문에 ||와 같은 문제를 만들지 않는다.

자세한 사항은 MDN 공식 문서를 참조하기 바란다.

Optional chaining - JavaScript | MDN

Nullish coalescing operator - JavaScript | MDN

Github: github.com/opwe37/Algorithm-Study/blob/master/LeetCode/src/191.js

opwe37/Algorithm-Study