【数据结构和算法】位图 BitMap

1. 位图结构的实现

/**
 * 位图数据类型 <br />
 * 位图以字节的一位为单位进行元素的操作，但是位运算以一个字节整体为运算单位，因此代码中以 bytes[index] 进行运算。
 * 位图元素的添加即找到相应的位置，将其置为1，实现时将该元素所在字节位与（1<<元素在字节所在位）求或即可；
 * 位图元素的删除即找到相应的位置，将其置为0，实现时将该元素所在字节位与(1<<元素在字节所在位)取反再求与即可；
 * 检查一个元素是否在位图中，实现时将该元素所在字节位与(1<<元素在字节所在位)求与后判断是否为0即可。
 *
 */
public class BitMap {
    private byte[] bytes;

    private int capacity;

    private static final int DEFAULT_CAPACITY = 32;

    public BitMap() {
        this(DEFAULT_CAPACITY);
    }

    public BitMap(int capacity) {
        this.capacity = capacity;
        this.bytes = new byte[(capacity >> 3) + 1];
    }

    /**
     * ADD
     *
     * @param num 元素
     */
    public void add(int num) {
        bytes[index(num)] |= (iterateByte(num));
    }

    /**
     * DELETE
     *
     * @param num 元素
     */
    public void delete(int num) {
        bytes[index(num)] &= (~iterateByte(num));
    }

    /**
     * 判断是否存在
     *
     * @param num 元素
     * @return 如果存在返回 true，否则返回 false
     */
    public boolean contains(int num) {
        return (bytes[index(num)] & iterateByte(num)) != 0;
    }

    /**
     * 计算 num/8
     *
     * @param num 运算数
     * @return 索引
     */
    private int index(int num) {
        return num >> 3;
    }

    /**
     * 获取元素字节所在位字节
     *
     * @param num 运算数
     * @return 1 左移 num%8 位 的结果
     */
    private int iterateByte(int num) {
        return 1 << (num & 0x07);
    }

    public byte[] getBytes() {
        return bytes;
    }

    public int getCapacity() {
        return capacity;
    }
}

2. 利用位图排序

public void sortByBitMap() {
	int[] arr = {4, 9, 2, 17, 3, 10};
	BitMap bitMap = new BitMap();
	for (int i : arr) {
		bitMap.add(i);
	}

	List<Integer> result = new ArrayList<>();
	byte[] bytes = bitMap.getBytes();
	for (int i = 0; i <bytes.length; i++) {
		for (int j = 0; j < 8; j++) {
			if ((bytes[i] & (1 << j)) == (1 << j)) {
				result.add((i << 3) + j);
			}
		}
	}

	System.out.println(result);
}