用位运算快速分解整数：从 LeetCode 2438 题谈起
在解决 LeetCode 2438 题（二的幂数组中查询范围内的乘积）时，核心步骤之一是将正整数
n分解为若干不同的 2 的幂之和，并存储到数组powers中。这个过程看似简单，但其高效实现依赖于位运算的一个关键技巧 ——lowbit运算。一、问题核心：分解 n 为 2 的幂数组
任何正整数
n都能唯一表示为若干不同 2 的幂之和（二进制的基本性质）。例如n=15的二进制为1111，对应1+2+4+8（即2^0+2^1+2^2+2^3），因此powers=[1,2,4,8]。二、高效分解工具：lowbit 运算
lowbit(x)的定义是：x 的二进制中最低位的 1 所对应的数值。例如x=14（二进制1110），最低位 1 对应 2，因此lowbit(14)=2。通过
lowbit分解n的步骤：- 初始化空数组
powers； - 当
n>0时，重复：- 用
lowbit = n & -n计算当前最低位 1 对应的数值； - 将
lowbit加入powers； - 用
n = n ^ lowbit（或n -= lowbit）移除已提取的 1，继续提取更高位的 1；
- 用
- 直到
n=0，powers即为分解结果。
示例：分解
n=15- 第一次提取：
lowbit(15)=1，powers=[1]，n=14； - 第二次提取：
lowbit(14)=2，powers=[1,2]，n=12； - 第三次提取：
lowbit(12)=4，powers=[1,2,4]，n=8； - 第四次提取：
lowbit(8)=8，powers=[1,2,4,8]，n=0。
三、关键位运算原理：为什么n & -n能求 lowbit？
这涉及计算机中负数的表示方式（补码）：
- 负数
-x的补码 =~x + 1（~x为按位取反，即翻转 x 的每一位二进制）； - 因此
n & -n的结果恰好保留了n二进制中最低位的 1，其余位为 0，即lowbit。
例如
n=12（二进制1100）：-12的补码为~12 + 1 = 0011 + 1 = 0100；12 & -12 = 1100 & 0100 = 0100（即4，正是lowbit）。
四、总结
利用
lowbit运算分解n为 2 的幂数组，时间复杂度仅为O(log n)（取决于n的二进制位数），是解决此类问题的高效方案。这一技巧不仅适用于本题，还广泛应用于树状数组、二进制分析等场景，是位运算中值得掌握的核心工具。