线性时间去重排序的位掩码实现
在某些特定场景下，例如对非负整数进行去重并排序，如果整数的范围不是特别大，可以考虑使用位掩码（bitmask）技术来实现接近线性时间的算法。其核心思想是利用一个大整数的位来标记数组中出现过的数字。如果数字 x 出现过，就将该大整数的第 x 位设置为1。
以下是一个Python实现的示例，用于对输入的非负整数列表进行去重和排序：
import numpy as np
from time import perf_counter
from numba import njit
def count_unique_and_sort(numbers):
"""
使用位掩码对非负整数进行去重和排序。
参数:
numbers: 包含非负整数的列表或NumPy数组。
返回:
一个包含去重并排序后的整数的列表。
"""
result = []
# m 用于存储位掩码，初始化为0
bitmask = 0
# 遍历输入数字，将对应位设置为1
for x in numbers:
# 确保 x 是整数，并将其对应的位设置为1
# 例如，如果 x 是 7，则 bitmask |= (1 << 7)
bitmask = bitmask | (1 << int(x))
# 从最低位开始检查，重建排序后的去重列表
current_bit_index = 0
while bitmask > 0:
# 如果当前位是1，说明对应的数字存在
if (bitmask & 1):
result.append(current_bit_index)
# 将位掩码右移一位，检查下一位
bitmask = bitmask >> 1
current_bit_index += 1
return result
# 性能测试
RNG = np.random.default_rng(0)
x = RNG.integers(2**16, size=2**17) # 生成大量随机非负整数
start = perf_counter()
y1 = np.unique(x) # NumPy的内置去重排序
print(f"NumPy unique took: {perf_counter() - start:.6f} seconds")
start = perf_counter()
y2 = count_unique_and_sort(x) # 自定义位掩码实现
print(f"Custom bitmask sort took: {perf_counter() - start:.6f} seconds")
print(f"Results match: {np.array_equal(y1, y2)}")在Python原生环境下运行上述代码，会发现自定义的 count_unique_and_sort 函数虽然逻辑正确，但其执行时间通常会比 np.unique 更长。这是因为Python的解释器开销较大，且 np.unique 底层由高度优化的C语言实现。
Numba优化尝试与遇到的问题
为了提升自定义函数的性能，我们自然会想到使用Numba这样的JIT（Just-In-Time）编译器。Numba可以将Python代码编译成机器码，从而显著提高计算密集型任务的执行速度。然而，当我们尝试将 @njit 装饰器应用于 count_unique_and_sort 函数时，却遇到了一个意想不到的问题：
from numba import njit
@njit # 取消注释此行，问题复现
def count_unique_and_sort_numba(numbers):
result = []
bitmask = 0
for x in numbers:
bitmask = bitmask | (1 << int(x))
current_bit_index = 0
while bitmask > 0: # 核心问题出在这里
if (bitmask & 1):
result.append(current_bit_index)
bitmask = bitmask >> 1
current_bit_index += 1
return result
# ... (与上面相同的测试代码，调用 count_unique_and_sort_numba)当 count_unique_and_sort_numba 函数被 @njit 装饰后，它不再返回正确的去重排序列表，而是返回一个空列表 []。这表明函数内部的逻辑在Numba编译后被破坏了。
问题根源：Numba的整数类型与位操作
这个问题的根源在于Python和Numba对整数类型的处理方式不同。
- Python的任意精度整数： Python中的整数是任意精度的，这意味着它们可以表示任意大小的整数，只要内存允许。例如，1 << 1000 在Python中是一个非常大的整数，不会溢出。
- Numba的固定大小整数： 为了实现高性能，Numba会将Python的整数转换为固定大小的机器整数类型，例如64位有符号整数（int64）。这种转换是性能优化的关键，但也引入了传统编程语言中常见的整数溢出问题。
具体分析：
在Numba的64位有符号整数表示中，最高位（第63位）用于表示符号。这意味着：
- 1 << 62 是一个正数。
- 1 << 63 会导致溢出，因为它的值超出了64位有符号整数的最大正数范围。在二进制补码表示中，1 左移63位的结果是一个负数（即 0x8000000000000000，表示最小的负数）。
我们可以通过一个简单的Numba函数来验证这一点：
from numba import njit
@njit
def shift_test(amount):
return 1 << amount
print("Numba 64位整数位移测试:")
for i in range(66):
value = shift_test(i)
print(f"1 << {i}: {value} (Hex: {hex(value)})")
if i == 63:
print(f" 注意：1 << 63 在Numba中变为负数，因为它是64位有符号整数的最小负值。")运行上述测试代码，你会发现当 i 等于 63 时，shift_test(63) 返回的值是一个负数。
为什么导致 while bitmask > 0 失败？
回到我们的 count_unique_and_sort_numba 函数： 当输入数组中存在大于等于63的整数时（例如，x = 63），bitmask = bitmask | (1 << int(x)) 这行代码中的 1 << int(x) 就会产生一个负数。由于 bitmask 是一个累积的结果，一旦它与一个负数进行按位或操作，其自身也可能变为负数（特别是当最高位被设置时）。
一旦 bitmask 变为负数，while bitmask > 0: 这个循环条件将立即变为假，导致循环体根本不会执行。结果就是 result 列表保持为空，函数最终返回一个空列表。
解决方案与注意事项
- 限制输入范围： 如果能够保证输入整数的最大值不超过62（即 2^63 - 1 的位掩码长度），那么这个位掩码方法在Numba中是可行的。然而，这大大限制了其通用性。
- 使用无符号整数（如果Numba支持）： 某些语言或库提供无符号整数类型，可以避免最高位作为符号位的问题。Numba目前对无符号整数的支持有限，通常会默认推断为有符号类型。
- 重新设计算法： 对于超出62的整数范围，位掩码方法不再适用。在这种情况下，应回归到更通用的排序和去重算法，例如基于哈希表（set）或基于排序（list.sort() 后遍历去重，或 np.unique）。虽然这些方法可能不是严格意义上的“线性时间”（例如，基于比较的排序通常是 O(N log N)），但在实际应用中它们更健壮且性能良好。
- 分块处理： 如果整数范围非常大，但稀疏分布，可以考虑将整数分块处理，或者使用字典（哈希表）来存储出现过的数字。
总结
Numba通过将Python的任意精度整数转换为固定大小的机器整数来提高性能，这在大多数数值计算中非常有效。然而，对于依赖于整数位操作且可能涉及大数值（特别是超过62的位移）的算法，开发者必须清楚这种类型转换带来的潜在问题。1 << 63 在Numba的64位有符号整数环境中会产生负数，从而导致依赖于 > 0 条件的位掩码算法失效。理解Numba的底层类型推断和数据表示是编写高效且正确Numba代码的关键。在设计算法时，应根据数据范围和特性，选择最合适的实现策略，而不是盲目追求某种“线性时间”的理论最优解。
