位图法：一种高效的排序去重策略
在处理非负整数的排序与去重问题时，如果整数的范围不是特别大，位图（bitmask）法是一种理论上可以达到线性时间复杂度的有效策略。其核心思想是利用一个大的整数（或位数组）的每一位来表示一个数字是否存在。
基本原理：
- 构建位图： 遍历输入数组中的每个数字 x。通过位或操作 m = m | (1
- 提取排序后的唯一元素： 从最低位（第0位）开始，逐位检查 m。如果第 i 位为1，则数字 i 是一个唯一的元素。将 m 右移一位 (m = m >> 1) 并递增 i，直到 m 为0。
以下是这种策略的Python实现示例：
import numpy as np
from time import perf_counter
from numba import njit
def count_unique_bitmask(ls):
"""
使用位图法对非负整数进行排序并去重。
该方法假设输入整数非负且在位图m所能表示的范围内。
"""
ret = []
m = 0 # 初始化位图，用于标记数字的存在
# 阶段1: 构建位图
for x in ls:
# 将数字x对应的位设置为1
# 例如，如果x=3，则m的第3位变为1
m = m | (1 << int(x))
# 阶段2: 从位图中提取排序后的唯一元素
i = 0
while m > 0: # 只要位图m中还有位是1，就继续
if (m & 1): # 检查当前最低位（第i位）是否为1
ret.append(i)
m = m >> 1 # 位图右移一位，准备检查下一位
i += 1 # 对应数字递增
return ret
# 示例测试
RNG = np.random.default_rng(0)
# 生成一个包含大量随机非负整数的数组，最大值2^16-1，数量2^17
x = RNG.integers(2**16, size=2**17)
print(f"输入数组大小: {len(x)}")
# 使用Numpy的np.unique进行基准测试
start = perf_counter()
y1 = np.unique(x)
print(f"np.unique 耗时: {perf_counter() - start:.6f} 秒")
# 使用纯Python实现的位图法进行测试
start = perf_counter()
y2 = count_unique_bitmask(x)
print(f"位图法 (Python) 耗时: {perf_counter() - start:.6f} 秒")
print(f"结果一致性检查: {np.array_equal(y1, y2)}")在上述测试中，纯Python实现的位图法通常会比高度优化的 np.unique 函数慢，因为Python解释器的开销较大。为了弥补这一性能差距，开发者常会考虑使用Numba这样的JIT（Just-In-Time）编译器来加速Python代码。
Numba加速尝试与意外行为
Numba通过即时编译Python函数为机器码，可以显著提升数值计算的性能。当尝试将上述 count_unique_bitmask 函数用 @njit 装饰器进行加速时，却出现了意料之外的结果——函数返回了一个空列表。
# ... (省略导入和RNG初始化)
@njit # 添加Numba JIT装饰器
def count_unique_bitmask_numba(ls):
"""
使用Numba加速的位图法，对非负整数进行排序并去重。
注意：此函数在特定条件下会遇到问题。
"""
ret = []
m = 0
for x in ls:
m = m | (1 << int(x))
i = 0
while m > 0:
if (m & 1):
ret.append(i)
m = m >> 1
i += 1
return ret
# 再次测试Numba版本
start = perf_counter()
y3 = count_unique_bitmask_numba(x)
print(f"位图法 (Numba) 耗时: {perf_counter() - start:.6f} 秒")
# 此时np.array_equal(y1, y3) 将返回 False，因为y3是空列表
print(f"结果一致性检查 (Numba): {np.array_equal(y1, y3)}")为什么Numba版本会失败并返回一个空列表？这涉及到Python和Numba在整数类型处理上的根本差异。
Numba中整数表示的陷阱：有符号64位整数
Python的整数是任意精度的，这意味着它们可以表示任意大小的整数，只要内存允许。这种灵活性是以性能为代价的。为了实现高性能，Numba通常会将Python整数编译为固定宽度的机器整数类型，默认为64位有符号整数（int64）。
问题就出在这个“有符号”特性上。在64位有符号整数表示中，最高位（第63位）被用作符号位。当这个位为1时，表示一个负数。
考虑位移操作 1
- 当 amount 小于 63 时，1
- 当 amount 等于 63 时，1
- 当 amount 大于 63 时，结果会因为溢出而截断或行为未定义，但通常也会导致负数或0。
为了验证这一点，我们可以运行一个简单的Numba测试程序：
from numba import njit
@njit
def shift_test(amount):
"""
演示在Numba中1左移操作对不同位数的行为，
特别是在64位有符号整数中的符号位影响。
"""
return 1 << amount
print("Numba中位移操作的行为:")
for i in range(66):
result = shift_test(i)
print(f"{i:2d}: {hex(result)} (十进制: {result})")
if i == 63:
print(" --- 注意: 1 << 63 在Numba int64中变为负数 ---")运行上述代码，你会观察到当 i 达到 63 时，shift_test(63) 返回的值是一个负数。
回到 count_unique_bitmask_numba 函数： 当输入数组 ls 中包含大于等于63的数字时，例如 x = 63，执行 m = m | (1 0: 这个循环条件将立即变为 False，导致循环提前终止。由于 ret 列表在循环开始前是空的，所以最终函数返回一个空列表。
结论与注意事项
- 位图法限制： 这种基于单个整数位图的排序去重方法，其能处理的最大数字受限于所用整数类型的位数。在Numba默认的 int64 环境下，它只能正确处理小于 63 的非负整数。对于大于等于63的数字，位移操作会导致位图 m 变为负数，从而破坏算法逻辑。
- Numba整数类型： Numba为了性能优化，默认使用固定宽度的有符号整数。进行位操作时，必须充分了解其底层数据类型的限制，尤其是涉及最高位的操作。
-
替代方案：
- 对于小范围整数（ 如果你确定所有数字都小于63，那么位图法在Numba中可以高效工作。
-
对于大范围整数： 如果数字范围超过63，位图法不再适用。你需要考虑其他更通用的方法：
- 使用 np.unique： Numpy的 unique 函数底层由高度优化的C代码实现，对于大多数情况，其性能表现都非常出色且稳定。
- 使用 set： Python的 set 数据结构天然支持去重。你可以先将列表转换为 set 进行去重，然后转换为列表并排序。Numba可以很好地处理Python的 set。
- 使用布尔数组： 创建一个足够大的布尔数组（例如 `seen = np.zeros(
