검 지 offer 프로 그래 밍 문제 (10): 이 진 중 1 과 0 의 개수

제목 설명
정 수 를 입력 하고 이 바 이 너 리 는 1 의 개 수 를 출력 합 니 다.그 중 음 수 는 부호 로 표시 한다.
이런 방법 은 속도 가 비교적 빠 르 고 그 연산 횟수 는 n 을 입력 하 는 크기 와 상 관 없 이 n 중 1 의 개수 와 만 관계 가 있다.n 의 바 이 너 리 표시 에 k 개 1 이 있다 면 이 방법 은 k 회 만 순환 하면 된다.그 원 리 는 n 의 바 이 너 리 표시 중 가장 오른쪽 에 있 는 1 을 계속 제거 하 는 동시에 계수 기 를 누적 하여 n 이 0 일 때 까지 코드 는 다음 과 같다.
int BitCount(unsigned int n)
{
    unsigned int c =0 ;
    for (c =0; n; ++c)
    {
        n &= (n -1) ; //       1
    }
    return c ;
}

왜 n & = (n – 1) 맨 오른쪽 에 있 는 1 을 지 울 수 있 습 니까?n 은 n - 1 의 최 하위 에 1 을 더 하 는 것 과 같 기 때문이다.예 를 들 어 8 (1000) = 7 (0111) + 1 (0001), 그래서 8 & 7 = (1000) & (0111) = 0 (0000), 8 의 가장 오른쪽 에 있 는 1 (사실은 가장 높 은 1, 8 의 바 이 너 리 중 하나 이기 때 문) 을 지 웠 다.예 를 들 어 7 (0111) = 6 (0110) + 1 (0001), 그래서 7 & 6 = (0111) & (0110) = 6 (0110), 7 의 바 이 너 리 표시 중 가장 오른쪽 에 있 는 1 (즉 가장 낮은 1) 을 지 웠 다.
int BitCount(unsigned int n) 
{     
    int m=0;   
    while(n)  
    {  
        n&=(n-1);  
        m++;  
    }  
    cout << m <return m;  
}

보충:
2 진수 중 0 의 개 수 를 구하 다
int BitCount(int x)  
{  
    int count = 0;  
    while (x + 1)  
    {  
        count++;  
        x |= (x + 1);  
    }  
    return count;  
}  

좋은 웹페이지 즐겨찾기