【位操作笔记】计算整数的绝对值 3

本文主要是介绍【位操作笔记】计算整数的绝对值 3，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

计算整数的绝对值(integer absolute) 3

用于计算整数的绝对值，不使用分支判断。

算法说明

CPU表示有符号数的是使用补码(two’s complement)，正数的补码与原码相同；负数的补码，符号位为1，其余位对原码取反加1。

如果CPU表示有符号数使用的是反码(one’s complement)，则该算法无效。

因为是使用补码(two’s complement)，所以有符号数右移，正数高位补0，负数高位补1，例如一个32位整数，右移31位，正数的结果为0x00000000，负数的结果则为0xFFFFFFFF。

因为算法的结果是带符号的，所以该算法在计算最大的负数时，结果依然会是负的。

实现代码

unsigned int bitabs(int val)
{unsigned int result;int const mask = val >> 31; //val >> (sizeof(int) * 8 - 1)result = val - ((val + val) & mask);return result;
}

或者

unsigned int bitabs(int val)
{unsigned int result;int const mask = val >> 31; //val >> (sizeof(int) * 8 - 1)result = val - ((val << 1) & mask);return result;
}

算法计算过程

第一步，计算mask

如果是正数，mask为0x00000000，既为0

如果是负数，mask为0xFFFFFFFF，既为-1

第二步，计算val + val 或者 val << 1

如果是正数，val + val 或者 val << 1 = 2val ，就是val×2。

如果是负数，val + val 或者 val << 1 = 2val ，就是val×2。

第三步，& mask

如果是正数，2val & mask = 2val & 0x00000000= 0。

如果是负数，2val & mask = 2val & 0xFFFFFFFF = 2val。

第四步，用val减去第三步的结果

如果是正数，val - 0 = val。

如果是负数，val - 2val = -val。

计算示例

假设是85 = 0b 0000 0000 0000 0000 0000 0000 0101 0101

mask = 85 >> 31 = 0val - ((val + val) & mask)
= 85 - ((85 + 85) & 0)
= 85 - (170 & 0)
= 85 - 0
= 85

假设是-85 = 0b 1111 1111 1111 1111 1111 1111 1010 1011

mask = -85 >> 31 = 0b 1111 1111 1111 1111 1111 1111 1111 1111 = 0xFFFFFFFFval - ((val + val) & mask)
= 85 - ((85 + 85) & 0xFFFFFFFF)
= 85 - (170 & 0xFFFFFFFF)
= 85 - 170
= -85