使用位图法(bitmap)，判断整数是否重复出现

使用位图法，记录海量签到数据，打卡数据。

package com;

/**
 * 题目:2.5亿个数字如何判断数字是否重复出现。
 * 
 * 解体思路：
 * 使用位图法，占位表示数字重复出现，
 * 一个int等于4个字节，1个字节8位，所以一个int可以表示32个数字。
 * 大于32使用数组存，每组32个数字。
 * 同时，题目要求表示重复出现，如果只用1个状态位，即只有0、1无法表示3状态(不存在、存在、重复)，
 * 即可以将状态位扩展到2位，就可以支持4种状态情况，00、01、10、11，
 * 相应的。将数组变成存16个即可。
 */
public class SpringBin {

    public static void main(String[] args) {
        setBit(100);
        setBit(101);
        setBit(102);
        setBit(100);
        System.out.println(getBit(100));
    }

    /**
     * 定义位图
     * 当前一位存放16个数字，假设数组长度为10，那么可以存放10 * 16 = 160个不同的数字.
     * 16000000即可以存放，16000000*16个数字。
     */
    static int[] bitmap = new int[16000000];


    /**
     * 1 1-2 00000000 00000011
     * 2 3-4 00000000 00001100
     * 3 5-6 00000000 00110000
     * 4 7-8 00000000 11000000
     * 5...
     *
     * 根据规律推导出公式：
     * (1 << (column * 2))      表示 10
     * (1 << (column * 2 - 1))  表示 01
     * @param data
     */
    public static void setBit(int data){
        int row = row(data);
        int column = column(data);

        if (getBit(data)) {
            //(1 << (column * 2)) 表示设置01
            bitmap[row] = bitmap[row] | (1 << (column * 2 - 1));
        }else {
            //(1 << (column * 2 - 1)) 表示设置10
            bitmap[row] = bitmap[row] | (1 << (column * 2));
        }
    }

    private static int row(int data){
        return data / 16;
    }

    private static int column(int data){
        return data % 16;
    }

    public static boolean getBit(int data){
        int row = row(data);
        int column = column(data);

        /**
         * 同理用公式判断是否存在10，存在重复
         */
        if ((bitmap[row] & 1 << (column * 2 - 1)) == 1 << (column * 2 - 1)){
            System.out.println(data + "重复key");
            return true;
        }

        /**
         * 同理用公式判断是否存在01，存在key
         */
        if ((bitmap[row] & 1 << (column * 2)) == 1 << (column * 2)
        ){
            System.out.println(data + "唯一key");
            return true;
        }


        System.out.println(data + "key不存在");
        return false;
    }
}