C++中如何高效实现数字或bitset的指定位区间翻转?
无循环的区间比特翻转实现
存在远优于逐位循环的高效实现,核心是利用CPU原生支持的位运算特性,以O(1)固定时间复杂度完成操作,没有循环带来的分支判断、迭代开销。
核心逻辑
异或运算天然适配单比特翻转的需求:
- 比特值与
1做异或,会自动完成翻转(01=1,11=0) - 比特值与
0做异或,会完全保留原值(00=0,10=1)
只需要构造一个目标掩码:需要翻转的区间内所有位填1,不需要改动的位全部填0,将原数和掩码做一次异或,即可一次性完成整个区间的翻转,全程不需要逐位循环。
通用掩码生成公式
统一采用从最右侧最低位开始、以0为起点的位索引规则,避免左起计数的歧义:
- 设待翻转区间内,权值最高的位对应的索引为
high_idx - 设待翻转区间内,权值最低的位对应的索引为
low_idx
对应的掩码可直接通过位运算生成,无需遍历:mask = (1 << (high_idx + 1)) - (1 << low_idx)
题目示例验证
对应题目中的6位二进制数100101,需翻转左数位置2到位置5的区间,预期结果为111011,操作流程如下:
- 位索引转换:6位二进制数的最高位(最左侧)对应权值2^5,即右起0基索引5,因此左数位置2对应右起索引4(high_idx=4),左数位置5对应右起索引1(low_idx=1)
- 计算掩码:代入公式得
(1 << (4+1)) - (1 << 1) = 32 - 2 = 30,对应二进制011110,刚好覆盖所有需要翻转的位区间 - 执行异或操作:原数
100101对应十进制值37,与掩码计算得37 ^ 30 = 111011,与预期输出完全一致
实现注意事项
- 需准确匹配高低位的索引值,索引错位会导致掩码覆盖错误的位区间
- 移位操作需匹配整数实际位宽,避免出现移位溢出的未定义行为(例如32位有符号整型的移位次数不能超过31)
内容的提问来源于stack exchange,提问作者Leena
相关产品推荐
相关产品推荐

