실전--수"1"의 개수

정수 의 이 진 을 구 하 는 것 은 몇 개의 1 을 포함 하 는 지 표시 합 니까?
변위 법

    /**
     *    
     *   n            1，       32 。
     *
     * @param x
     * @return
     */
    public static int bitShift(int x) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (1 == (x & 1)) {
                count++;
            }
            x >>= 1;
        }
        return count;
    }

위치 에 따라

    /**
     *    
     * 

     *     n&(n-1)，   n   1，      ，     1。
     * n          1，       。    ，n    32bit，  n        ，     16 1  ，    16 ，        。
     * 

     *               2 x  ，   return (n&(n-1)) == 0;  ，  n 2 x  ，         1。
     *
     * @param x
     * @return
     */
    public static int bitAnd(int x) {
        int count = 0;
        while (x > 0) {
            x &= (x - 1);
            count++;
        }
        return count;
    }

검표 법
1 차 검사 표

//          
result[1]=1;
result[2]=1;
result[3]=2;
…
result[58585858]=15;
…

public static int doubleSearchTable(int x) {
	return result[x];
}

시간 복잡 도 는 O(1)이 고 잠재 적 인 문 제 는 메모리 가 많이 필요 하 다 는 것 이다.
메모리 분석:메모리 2^32*5bit=2.5GB 필요
차 검사 표

	private static int num = (Short.MAX_VALUE + 1) * 2;
    //       
    private static byte[] countTable = new byte[num];

    static {
        // do init
        for (int i = 0; i < num; i++) {
            byte count = (byte) bitAnd(i);
            countTable[i] = count;
        }
    }
    
    /**
     *    
     *      ，            ，          ，        。
     * 

     *       O(1)，      ，       。
     *
     * @param x
     * @return
     */
    public static int doubleSearchTable(int x) {
        int n1 = x << 16 >>> 16;
        int n2 = x >>> 16;

//        PrintUtil.prettyPrint("n1:{} n2:{} ",n1,n2);

        return countTable[n1] + countTable[n2];
    }

메모리 분석:메모리 2^16*4bit=2.5GB 필요
검색 횟수
필요 한 메모리
1
2.5G
2
32KB
4
96B
8
4B
성능 비교

    public static void main(String[] args) {

        PrintUtil.dotRow();
        int times = CommonConstant.SIZE_M*100;

        PrintUtil.prettyPrint("       ：{}", times);
        Random r= new Random();

        // bitShift
        long start = System.currentTimeMillis();
        for (int i = 0; i < times; i++) {
            int x = r.nextInt(Integer.MAX_VALUE);
            int c1 = bitShift(x);
        }
        long interval = System.currentTimeMillis() - start;
        PrintUtil.prettyPrint("bitShift interval: {} ms", interval);


        // bitAnd
        start = System.currentTimeMillis();
        for (int i = 0; i < times; i++) {
            int x = r.nextInt(Integer.MAX_VALUE);
            int c2 = bitAnd(x);
        }
        interval = System.currentTimeMillis() - start;
        PrintUtil.prettyPrint("bitAnd interval: {} ms", interval);


        // doubleSearchTable
        start = System.currentTimeMillis();
        for (int i = 0; i < times; i++) {
            int x = r.nextInt(Integer.MAX_VALUE);
            int c3 = doubleSearchTable(x);
        }
        interval = System.currentTimeMillis() - start;
        PrintUtil.prettyPrint("doubleSearchTable interval: {} ms", interval);

        PrintUtil.dotRow();
    }

Result: …
성능 테스트 횟수:104857600 bitShift 간격:4080 ms bit And 간격:2186 ms doubleSearchTable 간격:1300 ms
…
Reference

https://mp.weixin.qq.com/s/A3dLW92SNag8lw7vrQiEHQ