常用接口接口功能size返回容器大小单位比特test返回给定数据对应比特位的状态为1返回true为0返回falseset将给定数据映射的的比特位设为1reset将给定数据映射的的比特位设为0面试题面试题 给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在 这40亿个数中。【腾讯】常规查找方法可以吗 比如用set解决排序二分查找答案是不行 我们来算算如果用常规的整数去处理需要多少空间40亿个整数大概占160亿比特位也就是16个G左右非常的夸张。位图解决数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使用一个二进制比特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0则代表不存在。将数据集{1, 3, 7,4,12, 16, 19, 13, 22, 18}映射到位图本质上是一个vectorchar的一个对象中:最后判断一个数在不在看其映射的byte位的值即可。模拟实现位图对于比特位数据的操作无非就是0和1直接修改或判断。因此位图的实现的核心思想是位运算。本文我们用vectorint作为载体实现位图代码语言javascriptAI代码解释templatesize_t N class Bitset { public: Bitset() { _a.resize(N / 32 1);//开好空间默认初始空间位32位 } //………… private: vectorint _a; };1. set具体逻辑查找该比特位在哪个整数中i x%32查找该比特位在整数的第几位j x/32将该整数与对应比特位为1且其余为0的整数按位或_a[i] | 1j