자바 소스 코드 Integer.bitCount 알고리즘 분석,분석 원리(통계 2 진 bit 비트)

알고리즘:정 수 를 집계 하 는 바 이 너 리 표현 식 의 bit 비트 가 1 인 자릿수(한 명 중량)
일반 알고리즘

public int bitCount(int num) {
    int count = 0;
    do {
        if ((num & 1) == 1) {
            count++;
        }
        num>>=1;
    } while (num > 0);
    return count;
}

가장 먼저 떠 오 르 는 알고리즘 일 것 입 니 다.최 하위 부터 한 사람 한 사람 이 1 인지,시간 복잡 도 는 O(n) 이 고 n 은 총 bit 수 입 니 다.
최적화 알고리즘

public int countBit2(int num) {
    int count = 0;
    while (num > 0) {
        num = num & (num - 1);
        count++;
    }
    return count;
}

이 알고리즘 은 얼핏 보면 어 리 석 지만 곰 곰 이 생각해 보면 원 리 를 발견 할 수 있다.n-1 후 n 의 최 하위 1 이 제거 되 었 고 n 비트 와 n 이 최 하위 1 에서 0 으로 변 한 후의 새로운 정수 이다.예 를 들 어:

0b101100      0b101011     1  ，0b101100 & 0b101011 = 0b101000

이렇게 몇 번 순환 하면 몇 개의 1 이 있 고 시간 복잡 도 역시 O(n) 이다.그러나 이 n 은 bit 비트 가 1 인 개 수 를 나타 내 고 전체적으로 이전 보다 좋 은 것 이다.우리 가 이것 이 이미 가장 좋 은 알고리즘 이 라 고 생각 했 을 때,사실은 그렇지 않 았 다.
Integer.bitCount

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

마지막 으로 자바 의 Integer 류 는 bit 비트 비트(기호 없 이 오른쪽으로 이동 하면 음 수 를 통계 할 수 있 는)를 통계 하 는 방법 을 제공 했다.얼핏 보면 WTF?원리:1 열의 1 이 우리 의 머 릿 속 에 놓 여 있 을 때 우 리 는 어떻게 세 나 요?하나의 숫자,첫 번 째 산법 의 원리.아니면 두 개,두 개?이 방법 은 이렇게 실현 되 었 다.다음 그림:

                                          
 1  0   1  1   1  1   1  1   1  1     10 11 11 11 11
  01     10     10     10     10       1 2  2  2  2
          \     /       \     /           \/    \/
  01       0100           0100         1   4    4
                \       /                   \  /
  01               1000                1      8
      \          /                       \   /
          1001                             9
          
              767      1       

각 두 비트 는 한 그룹 으로 각각 몇 개의 1 을 통계 한 다음 에 결 과 를 이 두 비트 에 저장 합 니 다.예 를 들 어 11 은 2 개의 1 이 있 고 결 과 는 10 이 며 10 을 대체 하여 원래 위치 에 저장 합 니 다.그리고 덧셈 을 해서 모든 결 과 를 더 해라.가 하 는 과정 에서 두 가 지 를 더 해 계산 절 차 를 줄 일 수 있다.
두 bit 계산 1 의 수량:11,0b11: 0b01 + 0b01 = 0b10 = 2,이렇게 하면 알 수 있다.
알고리즘 구현 은 다음 과 같 습 니 다.

우선 정수 i 는 왼쪽 한 자 리 를 지 운 다음 에 0b10: 0b01 + 0b00 = 0b01 = 1 을 더 했다.i & 0x55555555 은 왼쪽 을 오른쪽으로 옮 기 고 왼쪽 을 지우 면 두 비트 위의 1 의 개 수 를 계산 할 수 있다 고 말 했다.(i >>> 1) & 0x55555555 왼쪽 두 분 은 1 개,오른쪽 두 분 은 2 개 1 이 있다.

이때 0b1011=>0b0001 + 0b0101 = 0b0110 에 두 사람의 통계 결 과 를 저장 하여 두 사람 을 더 해서 마지막 으로 화 해 를 구 할 수 있다.

프로 세 스:

0x55555555  ‭0b01010101010101010101010101010101‬
0x33333333  ‭0b00110011001100110011001100110011‬
0x0f0f0f0f  ‭0b00001111000011110000111100001111‬
0x00ff00ff  0b00000000111111110000000011111111
0x0000ffff  ‭0b00000000000000001111111111111111‬
0x3f        ‭0b00111111‬

0b11 11 11 11 11    (i & 0x55555555) + ((i >>> 1) & 0x55555555)  = 0b0101010101‬ + 0b0101010101 = 0b1010101010
0b10 10 10 10 10    (i & 0x33333333) + ((i >>> 2) & 0x33333333) = 0b1000100010 + 0b00100010 = 0b1001000100
0b10 01 00 01 00    (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f) = 0b1000000100 + 0b0100 = 0b1000001000
0b10 00 00 10 00    (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff) = 0b1000 + 0b10 = 0b1010
0b00 00 00 10 10    (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff) = 0b1010 + 0 = 0b1010
dec           10

알고리즘 원형:

public static int bitCount(int i) {
    i = (i & 0x55555555) + ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f);
    i = (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff);
    i = (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff);
    return i;
}

시간 복잡 도 O(1),좋아,좋아!그러나 글 을 쓸 때 모두 윤색 해 야 한다.알고리즘 은 말 할 것 도 없고 최적화 한 후에 Integer 에서 의 실현 이다.최적화:

첫 번 째 단계:두 bit 계산 1 의 수량:i,0b11: 0b01 + 0b01 = 0b10 = 2.연구 결과:0b10: 0b00 + 0b01 = 0b01 = 1,2=0b11-0b1,한 번 줄 일 수 있 는 계산:1=0b10-0b1

두 번 째 단계:당분간 좋 은 최적화 방법 이 없다

세 번 째 단계:실제 적 으로 모든 byte 중의 1 의 수량 을 계산 하고 최대 8(0b 1000)개 로 4bit 를 차지 하 며 마지막 으로 비트 와 연산 소 위 를 할 수 있 으 며 i = i - ((i >>> 1) & 0x55555555) 연산 을 한 번 줄 일 수 있 습 니 다.&

제4,5 단계:같은 이유 로 마지막 에 소 위 될 수 있다.그러나 int 는 최대 32(0b 100000)개 1 이기 때문에 이 두 단 계 는 소 위 를 하지 않 아 도 되 고 마지막 단 계 는 필요 하지 않 은 bit 위 치 를 지우 면 된다.i = (i + (i >>> 4)) & 0x0f0f0f0f

깨 달 음:큰길 이 간단 하고 복잡 해 보 이 는 알고리즘,그 실현 원 리 는 우리 뇌의 간단 한 사고 논리 이다.

7    0b111
i = 7 - ((7>>>1) & 0x55555555) = 6 = 0b110
i = (6 & 0x33333333) + ((6 >>> 2) & 0x33333333) = 2 + 1 = 3 = 0b11
i = (3 + (i >>> 4)) & 0x0f0f0f0f = 3 & 0x0f0f0f0f = 3 = 0b11
i = 3 + (3 >>> 8) = 3 = 0b11
i = 3 + (3 >>> 16) = 3 = 0b11
i = 3 & 0x3f = 3