You need to enable JavaScript to run this app. C++中如何高效实现数字或bitset的指定位区间翻转?
优惠活动
大模型
产品
解决方案
定价
更多

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,操作流程如下:

  1. 位索引转换:6位二进制数的最高位(最左侧)对应权值2^5,即右起0基索引5,因此左数位置2对应右起索引4(high_idx=4),左数位置5对应右起索引1(low_idx=1)
  2. 计算掩码:代入公式得(1 << (4+1)) - (1 << 1) = 32 - 2 = 30,对应二进制011110,刚好覆盖所有需要翻转的位区间
  3. 执行异或操作:原数100101对应十进制值37,与掩码计算得37 ^ 30 = 111011,与预期输出完全一致

实现注意事项

  • 需准确匹配高低位的索引值,索引错位会导致掩码覆盖错误的位区间
  • 移位操作需匹配整数实际位宽,避免出现移位溢出的未定义行为(例如32位有符号整型的移位次数不能超过31)

内容的提问来源于stack exchange,提问作者Leena

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.10 16:54:04