一位对应一个可能成员
位集合是用位向量精确表示集合成员关系的数据结构。先为有限全集中的每个元素安排不同索引，再令相应位为1表示在集合内、为0表示不在。这里的关键是元素与位置的约定，不是数据恰好由二进制组成；一个没有这种语义的二进制文件并不会自动成为位集合。
以全集{0，1，2，3，4，5，6，7}为例，集合甲{1，3，6}只需将这三个位置置1。重复插入3不会增加成员数量，删除3则清零相应位。Java的BitSet提供读取、设置和清除等操作；其成员数cardinality与存储容量size、最高置位索引加一所得的length并不是同一概念。
把索引映射到机器字
常见稠密实现把连续位打包进机器字数组。设每字有w位，索引i位于下取整的i/w号字，字内偏移是i除以w的余数。读取时将该字与对应单位置1的掩码作按位与；设置用按位或，清除则与掩码的按位补作与。
OpenJDK的BitSet使用64位long存储，并明确采用上述映射。例如索引130落在从零编号的第2号字、偏移2处。这里的位编号约定不等于文件字节序；把内存结构保存或传给另一系统时，还须明确编码方式。若最高索引远大于成员数，直接位图仍要覆盖中间大片空位。
集合运算与字长成本
两个位集合必须共享同一元素编号，才可逐字进行交并运算。按位与得到交集，按位或得到并集，异或得到对称差。例如甲{1，3，6}与乙{3，4，6}的交集是{3，6}，并集是{1，3，4，6}。求补集还要限定全集范围，不能把最后一个字中未使用的高位误当成新成员。
在每次字访问和字运算为常数成本、全集大小为N的稠密数组模型中，单点查询为O(1)，完整逐字交并为O(向上取整的N/w)，原始位存储约为N位，另有取整和管理开销。因此一次机器指令能并行处理多位，并不意味着任意长的集合交集都只需常数时间。
扩容、稀疏性与概率过滤器
动态位集合也有增长成本。OpenJDK在容量不足时分配更大的字数组并复制旧内容，目标容量取原容量加倍与所需容量中的较大者；触及一个很高的新索引可能引发大块分配，不能把所有插入都当成最坏O(1)。这些是具体实现的行为，不是每种位集合共同承诺。
若集合十分稀疏，显式保存成员编号可能更省空间。Roaring的早期方案按块选择稀疏数组或稠密位图，说明压缩与随机访问可以组合设计，而成本取决于分布和实现。位集合也须与布隆过滤器区分：后者的肯定回答可能是假阳性；普通位集合只要编号无冲突且操作正确，就直接记录该元素是否存在。