검 지 offer 프로 그래 밍 문제 (10): 이 진 중 1 과 0 의 개수
2306 단어 프로 그래 밍 문제검지 제공
정 수 를 입력 하고 이 바 이 너 리 는 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
검지 Offer - 정렬: 빠 른 정렬먼저 배열 에서 무 작위 로 하나의 수 를 기준 으로 하고 끝의 요소 와 교환 하 며 마지막 요소 의 위치 에 놓 아 후기 비교 작업 을 편리 하 게 한다. 기준 보다 작고 기준 보다 큰 경 계 를 설정 하고 경 계...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.