核心概述：提供一个将长度 n 的排列在线性时间 O(n) 编码为整数的方案（不保持顺序），用于压缩存储与快速比较。
原文引述：
Description: Permutation → integer conversion. (Not order preserving.) Integer → permutation can use a lookup table. Time: O(n)
展开阐述：
-
定义与问题背景
- 问题：给定一个由 0..n-1 组成的排列，期望将其映射到一个整数表示，便于持久化、哈希、比较或与其他数据结构组合。
- 特性：“Not order preserving”表明该编码并非字典序秩或 Lehmer code 的有序对应，更多强调工程可用性与线性时间实现。
- 反向：原文提示“Integer → permutation can use a lookup table.”，意味着可用预先构建的查表法完成逆变换。
-
接口与核心变量（据实现习惯性命名）
- 输入：v（长度为 n 的排列，元素范围通常为 [0, n)）。
- 状态变量：
- use：位掩码，记录已出现的元素；
- i：当前位置计数，从 0 递增；
- r：累计的整数编码结果。
- 返回：整数 r，为该排列的编码值。
-
核心算法流程
- 初始化：use = 0，i = 0，r = 0。
- 逐个读入排列元素 x，执行：
- i 先自增：i ← i + 1；
- 用位运算结合 popcount 统计“在当前 x 之前已使用的元素个数”：
- cnt = popcount(use & -(1 << x))。
- 注意实现细节中的负号：-(1 << x) 是按补码意义取相反数（原注释强调“注意：是负号，不是 ~”），与 use 按位与后仅保留小于等于 x 的最低有效连续段，有助于得到计数。
- 累积编码：r = r * i + cnt；
- 标记已用：use |= (1 << x)。
- 最终 r 即为编码结果。
-
复杂度与边界条件
- 单次遍历 n 个元素，位运算与 popcount 在常数时间内完成，整体 O(n)。
- 位宽要求：当 n 较大时，use 的位数需覆盖最大元素值；对于 n > 64 的情形应改用更大位集或分块处理。
- 输入合法性：v 应为排列（元素不重复且范围合理），否则编码的可逆性与含义不再成立。
-
实现细节与易错点
- 负号语义：-(1 << x) 与 ~ 等价物不同，必须使用负号形成“低位屏蔽段”。
- popcount 语义：统计的是已用元素中“小于等于 x”一段的数量，确保计数稳定。
- 非保持顺序：不要将 r 误解为字典序秩；如需秩/逆秩，应使用相应的有序编码方案。
- 逆变换：根据“lookup table”提示，逆过程可通过预表或枚举构造，确保与此编码一一对应。
-
变体/扩展与工程实践
- 若需要“保持顺序”的秩编码，可考虑改为 Lehmer code 风格的乘阶展开；若只需压缩对比且强调线性常数，本实现足够简洁。
- 结合哈希：编码 r 可作为哈希键，或与 005-数据结构-哈希表 结合使用以加速查找。
- 大范围元素：若元素不是从 0..n-1 连续，则需先离散化到 [0..n-1]。
-
正确性直观
- r 通过“逐位进制扩展（基数依次为 1,2,…,n）+ 已用计数”累积形成，且 use 的递增与 popcount 的局部性保证每步信息不丢失；与固定的逆过程（查表）共同确保可还原。