32位C受限位运算：修复SigBitMask对0x80000000的错误

问题描述 #

这是C语言入门课程的受限编程任务，要求实现SigBitMask函数：

/*

• SigBitMask - 返回标记最高有效1位位置的掩码。若x == 0，返回0
• 示例: SigBitMask(96) = 0x40
• 合法操作: ! ~ & ^ | + << >>
• 最大操作次数: 16
• 难度评级: 4
  */

限制条件：

• 禁止使用分支/循环语句（do、if、while等）
• 禁止转换数据类型（包括unsigned）
• 禁止使用大于0xFF的常量（无法直接写0x80000000）
• 基于32位机器，禁止使用-、*等操作

用户现有代码：

int SigBitMask(int x) {
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  x = x ^ (x >> 1);
  return x & ~(x >> 1);
}

测试报错：

ERROR: Test SigBitMask(-2147483648[0x80000000]) failed...
...Gives 0[0x0]. Should be -2147483648[0x80000000]

问题根源 #

原逻辑只适用于正数，对负数的处理完全错误：

1. 当x是负数时，有符号数右移会自动填充符号位1，导致x |= x>>n的操作最终会把x变成全1（0xFFFFFFFF）。
2. 对全1的x执行x ^ (x>>1)会得到0，最后返回0，完全不符合要求。
3. 对于x=0x80000000（32位int的最小负数），同样会被处理成全1，最终返回0，触发测试错误。

修复方案 #

我们需要区分正负分别处理：

• 负数的最高有效1位固定是符号位（0x80000000），直接返回该值。
• 正数用原逻辑提取最高位掩码。
• x=0时返回0。

修复后的代码：

int SigBitMask(int x) {
  // 生成负数标识：x为负数时是0xFFFFFFFF，正数/0时是0
  int neg_flag = x >> 31;
  // 负数的结果：固定为0x80000000（用1<<31构造，1是合法小常量）
  int neg_result = (1 << 31) & neg_flag;
  
  // 处理正数：用~neg_flag把负数转为0，保留正数原样
  int pos_x = x & ~neg_flag;
  // 原逻辑：把最高位以下的位全置1
  pos_x |= pos_x >> 1;
  pos_x |= pos_x >> 2;
  pos_x |= pos_x >> 4;
  pos_x |= pos_x >> 8;
  pos_x |= pos_x >> 16;
  // 提取最高位掩码
  int pos_result = pos_x ^ (pos_x >> 1);
  
  // 合并结果：负数返回neg_result，正数返回pos_result，0返回0
  return neg_result | pos_result;
}

代码解释 #

1. 负数判断：x >> 31利用有符号数右移的特性，负数右移31位会得到全1（0xFFFFFFFF），正数/0得到全0。
2. 负数结果构造：1 << 31生成0x80000000，再和neg_flag做与运算，确保只有负数时返回该值。
3. 正数处理：x & ~neg_flag把负数转为0，正数保持不变，然后用原逻辑的移位或操作把最高位以下的位全置1，最后通过异或操作提取最高位掩码。
4. 结果合并：通过或运算自动选择对应结果，无需分支语句。

测试验证 #

• x=0x80000000：返回0x80000000，符合要求。
• x=-2：返回0x80000000，正确（最高有效1位是符号位）。
• x=96：返回0x40，符合示例。
• x=0：返回0，正确。

内容的提问来源于stack exchange，提问作者Josh