비트 수 계산 :이 행은 어떻게 작동합니까? n = n &(n-1);

Question

이 특정 라인이 어떻게 작동하는지 몇 가지 설명이 필요합니다.
이 함수는 1의 비트 수를 계산하지만이 행이 정확히 오른쪽 1 비트를 지우는 방법을 알고 있습니까?

int f(int n) { 
    int c; 
    for (c = 0; n != 0; ++c) 
     n = n & (n - 1); 
    return c; 
} 

간략하게 설명하거나 "증명"을 줄 수 있습니까?

Answer 1

임의의 부호없는 정수 n은 다음과 같은 마지막 k 자릿수를 갖습니다. 하나는 (k-1) 개의 0이 뒤에옵니다. 100 ... 0 k는 1 일 수 있으며 0 인 경우가 있습니다.

(N - 1)이 형식으로 끝날 : 제로 (K-1) (1)의 뒤에 : 011 ... (1)

N & (N-1) 따라서, 'K'제로로 끝나는 것 100 ... 0 & 011 ... 1 = 000 ... 0

그러므로 n & (n - 1)은 가장 오른쪽의 '1'을 제거합니다. 각각의 반복은 기본적으로 가장 오른쪽의 '1'자릿수를 제거하므로 1의 수를 계산할 수 있습니다.

Answer 2

나는 비트 조작을 닦아내어 이것을 보았습니다. 원래 포스터 (3 년 후)에 유용하지 않을 수도 있지만 다른 시청자의 품질을 향상시키기 위해 어쨌든 대답 할 것입니다.

n & (n-1)이 0 인 것은 무엇을 의미합니까?

루프를 깨는 유일한 방법이므로 (n != 0) 그 사실을 알고 있어야합니다. n=8을 예로 들어 보겠습니다. 그 비트 표현은 00001000입니다. n-1 (또는 7)의 비트 표현은 00000111이됩니다. & 연산자는 두 인수에 설정된 비트를 반환합니다. 00001000 및 00000111에는 유사한 비트가 설정되어 있지 않으므로 결과는 00000000 (또는 0)이됩니다. 숫자 8이 무작위로 선택되지 않았다고 생각할 수도 있습니다. 그것은 n이 2의 거듭 제곱 인 예입니다. 2 (2,4,8,16, 등)의 모든 힘은 같은 결과를 갖습니다.

지수가 2가 아닌 것을 전달하면 어떻게됩니까? 예를 들어, n=6, 비트 표현은 00000110 및 n-1=5 또는 00000101 국지적 인 &이 2 개 인자에 적용되고 그들은 단지 제로 그래서 우리는 c을 증가시키고하지 않습니다 4입니다 공통점이 하나의 비트, n=4을 가지고있다 동일한 프로세스가 n=4입니다. 앞에서 살펴 보았 듯이 4는 2의 지수이므로 다음 비교에서 루프를 중단합니다. 이 n까지 오른쪽 비트 2.

c은 무엇인가의 힘과 동일 차단 되는가?

그것은 단지 하나 모든 루프를 증가 및 0 c는 번호 앞에 잘라 비트 수가 긴 뺄셈과 "대출"에 대해 생각 2.