博客

今天看到有人说可以用位运算求绝对值，于是自己尝试推导了一下，然而没推出来。看了网上其他人的讲解，觉得这个问题很有意思，有必要记录一下。

在计算机基础课程里面我们知道，对于负数而言，原码转补码是 除符号位

取反加1

，补码转原码也是 除符号位

取反加1。

同时，如果我们求出了一个负数的原码，那么它的绝对值就很好求了，只需将这个原码的符号位取反即可（将1取反为0）。梳理一下，补码转原码时，除符号位都取反了，原码转绝对值时，符号位被取反了，那么，其实我们可以将这两次取反操作合在一起，即：对补码的

所有位

取反，然后

加1

，可得到该补码对应的

负数

的绝对值。

假设a是32位负整数，那么

• a的符号位是1，(a >> 31) 是 111…111，一共32个1，也就是
  
  -1的补码
  
  ，
• 
  和1进行异或
  
  相当于
  
  取反
  
  ，即 0 ^ 1 = 1，1 ^ 1 = 0，
• x
  
  + 1
  
  相当于 x
  
  – (-1)
  
  ，x是任意数，

那么

• 将a按位取反的算法是：a ^ (a >> 31)，
• 将a将位取反加1的算法是：(a ^ (a >> 31)) + 1 == (a ^ (a >> 31)) – (-1) == (a ^ (a >> 31)) – (a >> 31)。

对应的代码是：

int abs(int n) {
    int bits = sizeof(int) * 8 - 1;
    return (n ^ (n >> bits)) - (n >> bits);
}

其实这个算法同样适用于正整数求绝对值，因为，

假设b是32位正整数，那么

• b的符号位是0，(b >> 31) 是 000…000，一共32个0，也就是
  
  0的补码
  
  ，
• 
  和0进行异或
  
  相当于
  
  不变
  
  ，即 0 ^ 0 = 0，1 ^ 0 = 1，

那么

（b ^ (b >> 31)) – (b >> 31) == b。