프로그래밍 퀴즈 – 1의 개수

  • Post author:
  • Post category:칼럼
  • Post comments:0 Comments
  • Post last modified:January 25, 2016

문제

주어진 정수를 컴퓨터에서 내부적으로 표현할 때 1로 설정된 비트의 수를 반환하는 함수를 작성하라.

해결책 1

정수값에 따른 1의 개수를 미리 계산해놓는 방법이 있다.

int numOnesInBinary(int number)
{
    if(number == 0) return 0;
    if(number == 1) return 1;
    if(number == 2) return 1;
    if(number == 3) return 2;
    // 생략
}

이 방법은 유연성이 떨어질 뿐더러 평균 속도가 뒤이은 해결책 보다 느리다.

해결책 2

정수를 오른쪽으로 하나씩 시프트시킨다. 그래서 나온 값이 1이면 원래 정수에 비트 1이 하나 있었단 뜻이다. 이 과정을 정수의 비트 수만큼 반복하면 된다.

int numOnesInBinary(int number)
{
    int numOnes = 0;
    while(number != 0)
    {
        if( (number & 1) == 1 )
            numOnes++;
        number == number >>> 1; // 정수를 한 비트 오른쪽으로 시프트
    }
    return numOnes;
}

최악의 경우에 실행속도가 O(n)이다.

해결책 3

임의의 정수 number의 값이 01110000이라고 하자. 이때 number AND (number – 1)를 계산하면 어떻게 될까?

number AND (number - 1) 
= 01110000 AND (01100001)
= 01100000

이렇게 나온 정수에는 이전 정수보다 1의 개수가 하나 적다. 결과가 0이 될 때까지 위의 과정을 반복하면 1의 개수가 나온다.

int numOnesInBinary(int number)
{
int countOnes = 0;
        while (number != 0) {
            if ((number & 1) == 1)
                countOnes++;
            number = number >>> 1;
        }
        return countOnes;
    int numOnes = 0;
    while(number != 0)
    {
        number = number & (number - 1);
        numOnes++;
    }
    return numOnes;
}

이 방법은 실행속도가 O(m)에 불과하다. 그리고 m은 정수에 든 1의 개수다.

Author Details
Kubernetes, DevSecOps, AWS, 클라우드 보안, 클라우드 비용관리, SaaS 의 활용과 내재화 등 소프트웨어 개발 전반에 도움이 필요하다면 도움을 요청하세요. 지인이라면 가볍게 도와드리겠습니다. 전문적인 도움이 필요하다면 저의 현업에 방해가 되지 않는 선에서 협의가능합니다.
0 0 votes
Article Rating
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments