리트코드 - 191. Number of 1 Bits

리트코드 - 191. Number of 1 Bits

출처 - https://leetcode.com/problems/number-of-1-bits/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

부호 없는 정수의 이진 표현을 입력으로 받아 '1' 비트의 개수를 반환하는 함수를 작성하십시오. 이것은 Hamming weight로도 알려져 있습니다.

참고

 

• 일부 언어(예: Java)에서는 부호 없는 정수 유형이 없을 수 있습니다. 이 경우, 입력은 부호 있는 정수 유형으로 제공됩니다. 그러나 이것은 구현에 영향을 미치지 않아야 합니다. 정수의 내부 이진 표현은 부호가 있든 없든 동일합니다.
• Java에서 컴파일러는 2의 보수 표기법을 사용하여 부호 있는 정수를 표현합니다. 따라서 예시 3에서 입력은
• 일부 언어(예: Java)에서는 부호 없는 정수 유형이 없을 수 있습니다. 이 경우, 입력은 부호 있는 정수 유형으로 제공됩니다. 그

의사코드

countNumberOne = 0 반복문 시작 (32번 반복)     if ((n & 1) == 1)         countNumberOne을 1 더함     n = n >> 1 반복문 종료 countNumberOne 리턴

 

풀이코드

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int countNumberOne = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & 1) == 1) {
                countNumberOne++;
            }
            n = n >> 1;
        }
        return countNumberOne;
    }
}

 

코드설명

비트 연산자를 이용한 풀이이다.

n의 마지막 자리를 확인해서 1이면 countNumberOne 을 더하고, n을 오른쪽으로 한칸 밀어서 다시 확인하는 코드이다.

 

최종적으로 countNumberOne을 리턴하면 된다.

 

시간복잡도 - O(1)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

이전문제와 비슷하게 구현했으나 생각보다 메모리 효율이 좋지 못했다(약 60%)

다른 코드들을 찾아보니 일반 우측 쉬프트(>>) 말고 논리 우측 쉬프트(>>>) 연산자가 있었다.

자바 책에서 봤던 것 같음...

 

논리 우측 쉬프트의 차이점?

논리 우측 쉬프트는 부호를 고려하지 않고 오른쪽으로 당긴다음 0으로 채운다.

이에반해 일반 우측 쉬프트는 부호를 고려하여 계속 1을 추가하게 된다.

 

예를 들어 1111 1111 1111 1111 1111 1111 1111 1011 이라는 이진수가 있다면

 

>>> 를 사용하면

0111 1111 1111 1111 1111 1111 1111 1101 이 되지만

>> 을 사용하면 부호를 고려하여

1111 1111 1111 1111 1111 1111 1111 1101 이렇게 되는 것이다.

 

리팩토링

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int countNumberOne = 0;
        while (n != 0) {
            if ((n & 1) == 1) {
                countNumberOne++;
            }
            n = n >>> 1;
        }
        return countNumberOne;
    }
}

이를 활용하여 위와같이 로직을 짰으나 의외로 메모리는 줄지 않았다.

그래서 다른 코드를 찾아보니 유명한 알고리즘이 있었다.

 

브라이언 커니핸 알고리즘(Brian Kernighan's Algorithm)

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int countNumberOne = 0;
        while (n != 0) {
            n = n & (n - 1);
            countNumberOne++;
        }
        return countNumberOne;
    }
}

n & (n - 1) 부분이 재밌는 부분이다.

예를 들어 1011 이라는 수가 있다면 n-1 이 된 값은 1010이 될 것이다.

두개의 & 연산을 하게되면 정확하게 마지막 자리만 삭제가 된다.

 

다시 반복문을 돌면 1010에서 1이 또 빠진값인 1001이 된다.

1010과 1001 을 & 연산을 하면 1000이 되고, 이를 다시 1을 빼는 연산을 하면 0100이 된다.

둘의 & 연산 결과는 0이고 이때의 countNumberOne 값은 3이다.

 

굳이 >>> 연산을 쓰지 않고도 끝자리에서부터 하나씩 1을 지워나갈 수 있다.

 

하지만....모든 코드(리팩토링과 브라이언 커니핸 알고리즘 모두)의 메모리는 똑같거나 효율이 더 안좋았다 😂

런타임이 모두 0ms인 것에 만족해야겠다...

 

정리

2진수에서 1을 세는 여러가지 방법