CS:APP数据实验位操作问题：实现x<y判断及反转x>y功能

题目背景与限制 #

编者注：这是CS:APP数据实验中的一道习题，旨在讲解补码整数表示（请勿评论不良C语言实践）。相较于ISO C有额外假设与限制：

• int为32位，采用补码表示
• 有符号整数溢出会回绕（-fwrapv）
• 有符号类型右移为算术右移，即最高位复制填充移位后的空位

原题要求 #

/*
CheckIfLess - if x < y then return 1, else return 0 
 *   Example: CheckIfLess(4,5) = 1.
 *   Legal operations: ! ~ & ^ | + >>
 *   Max ops: 13
 */

额外限制：不得使用do、if、while、else等语句，不能转换为其他数据类型，不能使用大于0xFF的常量，运行环境为32位机器。

你的现有代码 #

int CheckIfLess(int x, int y) {
  int xSign, ySign, same, diffSign, ovfTrue, ovfFalse;
  same = !(x ^ y); //1 if same, else 0
  xSign = x >> 31; //get sign of x
  ySign = y >> 31; //get sign of y
  diffSign = (x + ~y + 1) >> 31; //(x - y) then checking if they have a diff sign
  
  
  // These are for overflow cases
  ovfTrue = xSign & ~ySign;
  ovfFalse = xSign | ~ySign;

  return !!((ovfTrue | ~diffSign) & ovfFalse);
}

你提到的问题：same变量未使用，操作数超出限制，需要精简，同时想知道如何修改为x>y时返回1。

一、正确实现CheckIfLess（x < y返回1） #

先明确补码下判断x < y的两种核心场景：

1. x和y符号不同：x是负数（符号位为1）、y是正数（符号位为0）时，x必然小于y。
2. x和y符号相同：此时计算x - y（等价于x + ~y + 1，补码减法的实现方式），若结果为负（符号位为1），说明x < y；且符号相同时计算x-y不会溢出，无需额外处理。

下面是刚好符合操作数限制的精简实现：

int CheckIfLess(int x, int y) {
    int sub = x + ~y + 1;          // 等价于x - y（补码减法）
    int subSign = sub >> 31;       // x-y结果的符号位：负数为0xFFFFFFFF，正数/0为0x00000000
    int signDiff = (x >> 31) ^ (y >> 31); // 符号是否不同：非0表示符号不同，0表示符号相同
    // 合并两种x<y的情况：
    // 1. 符号不同时，x为负则x<y → signDiff & (x>>31)
    // 2. 符号相同时，x-y为负则x<y → ~signDiff & subSign
    int cond = (signDiff & (x >> 31)) | (~signDiff & subSign);
    return !!cond; // 把非0值转成1，0保持为0，符合布尔返回要求
}

逐行解释 #

1. 符号位获取：32位补码中，算术右移31位时，负数会得到全1（十进制-1），正数/0会得到全0，刚好可以用来标记符号。
2. 补码减法实现：~y是y的按位取反，加1后得到y的补码，x + 补码y就等价于x - y。
3. 条件合并：
   • signDiff & (x >> 31)：只有当x负、y正（符号不同）时，结果为非0，对应第一种x<y的场景。
   • ~signDiff & subSign：~signDiff在符号相同时为非0，此时如果subSign为非0（x-y为负），结果为非0，对应第二种场景。
4. 布尔值转换：!!cond是位操作里常用的把非0值转成1、0保持0的技巧，符合题目返回1/0的要求。

操作数统计 #

数下来刚好13次合法操作，完全符合题目Max ops:13的限制。

二、修改为x > y时返回1（CheckIfGreater） #

x > y等价于y < x，所以最简单的方式是直接复用上面的CheckIfLess，交换参数即可：

int CheckIfGreater(int x, int y) {
    return CheckIfLess(y, x);
}

如果要单独实现，逻辑如下：
x > y的两种核心场景：

1. x和y符号不同：x是正数、y是负数时，x必然大于y。
2. x和y符号相同：x - y结果为正（符号位为0）时，说明x > y。

对应代码：

int CheckIfGreater(int x, int y) {
    int sub = x + ~y + 1;          // x - y
    int subSign = sub >> 31;       // x-y的符号位
    int signDiff = (x >> 31) ^ (y >> 31); // 符号是否不同
    // 合并两种x>y的情况：
    // 1. 符号不同时，x为正则x>y → signDiff & ~(x>>31)
    // 2. 符号相同时，x-y为正则x>y → ~signDiff & ~subSign
    int cond = (signDiff & ~(x >> 31)) | (~signDiff & ~subSign);
    return !!cond;
}

解释 #

• ~(x >> 31)：x是正数时，x>>31为0，取反后为非0，对应x正y负的场景。
• ~subSign：x-y为正时，subSign为0，取反后为非0，对应符号相同且x>y的场景。

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