位图数据结构

1.位图的概念

位图就是指由二进制位组成的数据结构。例如可以做标记处理。比如1个byte占用8个字节那除去符号位那么1个字节就可以表示8个状态位。

位图在算法中还是用的比较多因为是基于二进制操作运算速度比较快。比如在leetcode中的一道题目是 判定字符是否唯一那么我们借助位图就可以进行如下判断

    public static boolean isUnique(String str) {
        long bits = 0;
        int size = str.length();
        for (int i = 0; i < size; i++) {
            int move = str.charAt(i) - 'A';
            if ((bits & (1L << move)) != 0) {
                //有重复的直接返回false
                return false;
            } else {
                //标记当前位置有这个字符
                bits |= (1L << move);
            }
        }
        return true;
    }

2.位图常用操作

public class BitTest {
    public static void main(String[] args) {
        System.out.println(onOff(32,0));
    }
    // 查询 第n个位置是否为1
    public static boolean contains(int x,int n){
        return (x &(1<<n))!=0;
    }
    // 将第n位设置为1
    public static int  setBitOne(int x,int n){
        return x | (1<<n);
    }
    // 将第n位设置为0
    public static int  setBiZero(int x,int n){
        return x &~ (1<<n);
    }
    // 将这个数的从右往左数的所有位设置为1
    public static int setRightToLeftOne(int x){
        return x|(x-1);
    }

    // 把number的二进制中从右往左数的最后一位0变成1
    public static int setRightToLeftZero(int x){
        return x|(x+1);
    }
    // 对n位取反,n从0开始
    public static int onOff(int x,int n){
        return x^(1<<n);
    }
}