怎么用逻辑右移实现算术右移？

Question

怎么用逻辑右移实现算术右移？修改

用逻辑右移实现算术右移。
csapp第二章章末习题。
禁止使用条件，循环语句，禁止使用右移和取模运算。

int sar (int x, int k)
{
     int xsrl = (unsigned)x >> k;
     // 接下来怎么办？
     
}

Answer 1

int sar (int x, int k)
{
    int xsrl = (unsigned) x >> k;
    
    int len = sizeof(int) * 8;
    
    int mask = 1 << (len - k - 1);
    
    return (xsrl ^ mask) - mask;
}

Answer 2

不是不给用右移么？怎么你代码又有。。

提示:

• 右移一位约等价于除以2

• 用递归代替循环

Answer 3

事实上这个题目是不允许强制类型转换/条件分支/循环的。。。
一切都只能通过位运算完成，另外使用的常数也不能超过255
就是说在写完答案后不能仅仅make btest + ./btest funcion_name，还应该用./dlc bits.c检测下是否合法。特别提一下dlc，这里作者非常用心的写了个parser检测是否合法。

logicalShift

• 总体思路是将1左移31位然后右移n-1位从而计算出掩码，然后(x>>n)&mask即可得出答案
• IA32下不能够偏移超过31位，会在cl寄存器中限定移动位数为0-31，也就是说移动32位不是置0，而是不移动

//  错误代码示例
int mask = 1 << 31 >> (n + (~1 + 1));
return (x>>n) & mask;
// n = 0时会出错

• 使用一种另类的条件!!n，它会在n=0时返回0，n!=0返回1，使用（!!n)&1的返回值，我们就相当于对两种情况做了下分类n==0?n=0:n=1;

答案

int logicalShift(int x, int n) {
  /**
   * can not shift more than 31 bits
   * mask computation:
   * (1) left shift 1 to the leftmost bit
   * (2) right shift the number in step in (1) for n-1 bits
   * since IA32 will rotate the shift number to 32
   * (which means we are able to shift 31 bits at most)
   * we cannot just implement it as above
   * ====
   * !!n act as a condition, when n=0 it returns 0, otherwise 1
   * so we shift (!!n) and solve the IA32 feature
   * ====
   * here is the wrong code:
   * mask = 1 << 31 >> (n + (~1 + 1));
   * when n = 0, it will not shift at all
   */
  return (x>>n)&(~(((!!n) & 1)<<31>>(n+(~1+1))));
}