독서 노트

제목 설명


정수를 입력하여 바이너리 중 1의 개수를 출력합니다.그중의 음수는 부호를 보충하여 표시한다.

문제풀이의 방향


사고방식1: 이 정수를 처리한다.정수 2진법이 표시하는 가장 오른쪽의 한 자리가 1인지 아닌지를 판단하고 이 정수가 1(선별인자)과 맞물려 오른쪽으로 한 자리를 옮긴다.
int count = 0;
while ( n ) {
    if ( n & 1 ) {
        count++;
    }
    n = n >> 1;
}
return count;

사고방식2: 이 정수를 처리한다.사고방식 1의while 순환을 for 순환으로 바꾸면 사순환 문제를 해결할 수 있다.for 순환에서 먼저 정수를 계산해 냅니다.
const size_t bitsInByte = 8;
int count = 0;
for (size_t i = 0; i < sizeof(int)*bitsInByte; i++ ) {
    if ( n & 1 ) {
        count++;
    }
    n >>= 1;
}
return count;

사고방식 3: 선별 인자 처리.사고의 결함을 피하기 위해서 우리는 숫자 1에 대해 손발을 놀릴 수 있다.숫자 1과 이 정수의 마지막 위상이 맞으면 숫자 1을 왼쪽으로 한 자리 옮긴다.순환 횟수는 정수 이진법의 자릿수 32이다.
int count = 0;
int flag = 1;
while ( flag ) {
    if ( n & flag ) {
        count++;
    }
    flag = flag << 1;
}
return count;

사고방식4: 처리 정수 마지막 1.매번 마지막 하나만 처리한다.1. 정수에서 1을 빼면 어떤 변화가 생길까?이진법은 마지막 하나가 0이 되고 원래 1 뒤의 0이 1이 된다는 것을 나타낸다.예를 들어 이진수 10101000에서 1을 빼면 10100111이 된다.2. 1을 뺀 숫자가 원수와 맞물리면 마지막 1은 0이 되고 마지막 1보다 높은 자리는 변하지 않는다.예를 들어 10100111 & 101010000의 결과는 10100000이고 마지막 1은 0이 되었다.참고 코드 참조.

참조 코드

class Solution {
public:
     int  NumberOf1(int n) {
        int count = 0;
        while ( n ) {
            count++;
            n = (n-1)&n;//     1 0
        }
        return count;
     }
};

좋은 웹페이지 즐겨찾기