C# 프로그래밍 기초 실습 전자책

C# / .NET 알고리즘과 퀴즈
본 알고리즘 퀴즈 문제는 C#/.NET 개발자를 위한 알고리즘 인터뷰 혹은 C# 프로그래밍을 통한
문제 해결 알고리즘을 연구해 보는데 도움이 되고자 작성되었습니다.


퀴즈 질문


예상답변/설명

정수에 포함된 bit 1의 갯수는 한 비트씩 검사해서 32비트를 차례로 검사하여(아래 GetNoOfBits1() 함수) 전체 갯수를 구할 수 있다. 보다 나은 방식으로 n과 n-1의 값을 AND 연산하는 것으로 이는 가장 오른쪽에 있는 bit 1을 0로 만드는 효과가 있다. 예를 들어, n=001100인 경우 n-1=001011이 되며, n AND n-1은 001000 이 된다. 이러한 방식으로 가장 오른쪽의 bit 1을 계속 지워나가면, 32번의 루프를 돌 필요가 없다.

int GetNoOfBits1(int n)
{       
    int count = 0;
    for(int i=0; i<32; i++)
    {
        count += (n & (1 << i)) != 0 ? 1 : 0;
    }
    return count;
}

int GetNoOfBits2(int n)
{
    int count = 0;
    while(n != 0)
    {
        n = n & (n - 1);
        count++;
    }
    return count;
}