검 지 offer:이 진 중 1 의 개수(비트 연산)

제목.
정 수 를 입력 하고 이 32 비트 바 이 너 리 는 1 의 개 수 를 출력 합 니 다.그 중 음 수 는 부호 로 표시 한다.tip:양수 패 치 는 원 코드 이 고 음수 의 패 치 는 양수 패 치-1 반)
예시
입력:11 출력:3 해석:입력 한 11,바 이 너 리 는 00000000000000000000000001011 로 모두 세 자리 가'1'입 니 다.
코드
해법
자바 API 함수 사용
1.bitCount

public class Solution {
     
    public int NumberOf1(int n) {
     
        return Integer.bitCount(n);
    }
}

2.toBinaryString

public class Solution {
     
    public int NumberOf1(int n) {
     
        String s = Integer.toBinaryString(n);
        int count = 0;
        for(int i=0;i<s.length();i++){
     
            if(s.charAt(i) == '1'){
     
                count++;
            }
        }
        return count;
    }
}

해법
비트 연산
1.마스크
우 리 는 숫자의 32 자 리 를 두루 훑 어 보 았 다.만약 한 사람 이 11 이 라면,계수 기 를 하나 더 넣 어 라.우 리 는 비트 마스크 를 사용 하여 숫자의 i 위 를 검사 합 니 다.처음에 마스크 m=1 은 1 의 바 이 너 리 가 0000 0000 0000 0000 00001 이 라 고 표시 하기 때문에 모든 숫자 와 마스크 11 이 논리 적 이 고 연산 을 하면 우 리 는 이 숫자의 가장 낮은 위 치 를 얻 을 수 있다.다음 위 치 를 검사 할 때,우 리 는 마스크 를 왼쪽으로 한 명 옮 길 것 이다.0000 0000 0000 0000 0000 0010 이 과정 을 반복 합 니 다.

public class Solution {
     
    public int NumberOf1(int n) {
     
        int count = 0;
        int mask = 1;
        for(int i=0;i<32;i++){
     
            if((n & mask) != 0){
     
                count++;
            }
            mask = mask << 1;
        }
        return count;
    }
}

2.비트 조작
만약 하나의 정수 가 0 이 아니라면,이 정 수 는 적어도 한 명 은 1 이다.만약 우리 가 이 정 수 를 1 로 줄 이면 원래 정수 맨 오른쪽 에 있 던 1 은 0 으로 변 하고 원래 1 뒤에 있 던 모든 0 은 1 로 변 한다(맨 오른쪽 에 있 는 1 뒤에 0 이 있다 면).나머지 모든 분 들 은 영향 을 받 지 않 을 겁 니 다.예 를 들 어 하나의 이 진수 1100,오른쪽 부터 세 번 째 는 가장 오른쪽 에 있 는 1 이다.1 을 뺀 후 3 위 는 0 이 되 었 고,그 뒤의 두 분 은 0 이 1 이 되 었 으 며,앞의 1 은 변 하지 않 았 기 때문에 얻 은 결 과 는 1011 이 었 다.우 리 는 1 을 뺀 결 과 는 맨 오른쪽 에 있 는 1 을 시작 한 모든 사람 을 반대로 한 것 을 발견 했다.이때 우리 가 원래 의 정수 와 1 을 뺀 후의 결 과 를 다시 연산 하면 원래 의 정수 오른쪽 에 있 는 1 명 부터 모든 자리 가 0 이 된다.예 를 들 어 1100&1011=1000.즉,하나의 정 수 를 1 로 줄 이 고 원래 의 정수 와 연산 을 하면 이 정수 의 맨 오른쪽 에 있 는 1 을 0 으로 바 꾸 는 것 이다.그러면 하나의 정수 의 이 진 은 몇 개의 1 이 있 으 면 몇 번 이나 이런 조작 을 할 수 있다.

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