负数的算术右移有什么规律？

Question

/* 
 * divpwr2 - Compute x/(2^n), for 0 <= n <= 30
 *  Round toward zero
 *   Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int divpwr2(int x, int n) {
    int div =(x + ((x >> 31) & ((1 << n) + ~0))) >> n;
    return div;
}

我的问题是答案的算式为什么那样写？

就是这一步

div =(x + ((x >> 31) & ((1 << n) + ~0))) >> n;

另外，问下负数在算术右移过程中有什么规律吗？

Answer 1

你要知道原码和补码的概念，还有符号位。原码的数值部分是无符号的二进制数，正数的符号位是0，负数的符号位是1；补码的话，简单说一下，正数和原码一样，但是负数是原码的数值部分各位取反，末位加一。

计算机里我们看到的和用的数字都是原码，而底层一般都是用补码实现的，例如，-10的原码是[1]1010(假设符号位是一位[]),补码是[1]0110，算数右移一位变成[1]1011（因为是补码，算术右移，首位补符号位），这个数转换成原码是 [1]0101，也就是 -5，再移一位为[1]1101,转换成原码是[1]0011，是 -3.以此类推，至于规律，我也不知道有什么规律，不过移动的位数如果超过了数值所有位数，结果会是-1.

Answer 2

楼上说的很对，右移就是这样的。
如果你仔细观察一下规律，你会发现：

    对于任一一个整数n，n >> x 的结果是n/(2^x)，如果出现小数，结果就取小于它的最大整数。(至于证明我也不知道，但这个规律很好用，而且和左移的规律有点像)