请现场手写实现一个 Bitmap 结构，并说明其核心原理和适用场景。

回答思路

1. 【回答框架 1】Bitmap 是一种基于位运算的紧凑数据结构，用每一位（bit）表示一个元素是否存在，常用于海量数据的去重、排序和快速查询。其核心思想是用一个字节数组或长整型数组作为底层存储，通过索引计算出元素所在的字节位和位偏移。
2. 【回答框架 2】实现时通常定义一个 byte[] 或 long[] 数组，初始化时指定容量（最大元素值）。核心操作包括 set（将某位置为 1）、get（判断某位是否为 1）和 clear（将某位置为 0）。计算索引时，先按位右移得到数组下标，再对 8 或 64 取模得到位偏移，最后用位或、位与等操作完成读写。
3. 【回答框架 3】以 long[] 为例，对于非负整数 n，数组索引为 n >> 6，位偏移为 n & 63。set 操作为 arr[n >> 6] |= (1L << (n & 63))；get 操作为 (arr[n >> 6] & (1L << (n & 63))) != 0；clear 操作为 arr[n >> 6] &= ~(1L << (n & 63))。注意使用无符号右移以支持大索引。
4. 【回答框架 4】Bitmap 在内存占用上远优于布尔数组，例如存储 10 亿个整数只需约 125MB（若用 long 数组则约 125MB，若用 byte 数组则约 125MB，实际取决于实现）。适用于海量整数去重、Bloom Filter 的底层、操作系统内存页管理、数据库位图索引等场景。但仅能表示存在性，不能存储重复次数或其他附加信息，且对稀疏数据可能不如哈希表。
5. 【回答框架 5】实现时需明确容量边界，处理索引越界；若需要动态扩容，可在数组满时重新分配并拷贝。复杂度上，set/get/clear 均为 O(1)，空间复杂度为 O(N/位数)。
6. 【关键点 1】Bitmap 用位存储存在性，set/get/clear 均为 O(1) 位运算。
7. 【关键点 2】索引计算：long 数组下标为 n>>6，位偏移为 n&63。
8. 【关键点 3】适用于海量整数去重、布隆过滤器底层，但不能表示重复计数。
9. 【关键点 4】内存占用为最大值/8 字节（byte 实现）或最大值/64 字节（long 实现）。
10. 【关键点 5】需处理容量边界与越界，动态扩容需重新分配并拷贝数组。
11. 【易错点 1】容易混淆字节与比特的换算，导致内存估算错误。
12. 【易错点 2】未处理负数索引，直接使用右移可能产生错误结果。
13. 【易错点 3】无符号右移与有符号右移的混淆，可能导致高位数据错误。