Solution

One solution that is easily found on the internet looks as follows:

const int BitsPerByte = 8;

inline unsigned int abs (const int& number)
{
   int const mask = number >> (sizeof(int) * BitsPerByte - 1);

   return ((number + mask) ^ mask);
}

It is certainly not the best example of readable and self-documenting code, but it leverages some basic yet very important insights that are not fully understood by most software engineers.

What Does It Do?

Nearly all processor architectures use the Two’s Complement to represent negative integers, because it allows the addition and subtraction hardware to be implemented in a way that is independent of a number’s sign. Although the C and C++ standards do not enforce this architectural feature, it is pretty safe to assume that it will be present, particularly on PC and game console platforms.

Assuming that the most significant bit of an integer is used as the sign, where 1 indicates a negative number and 0 indicates a positive number, the Two’s Complement of a number is calculated by inverting all its bits (the so called One’s Complement) and then adding the number 1. For example, the 8-bit binary representation of the decimal number 122 is 01111010, flipping all its bits creates 10000101 and adding 1 results in 10000110, which is decimal -122 (the sign bit is printed in bold).

In order to calculate the absolute value of a number, we basically have to calculate the Two’s Complement if and only if the number is negative. The pseudo code for this algorithm could look as follows:

if (number is negative)
   return Two`s Complement of number
else
   return number

For negative numbers, the algorithm would take three steps: a conditional branch, a negation for the One’s Complement and an addition for the Two’s Complement. By leveraging some characteristics of the bit-wise XOR (exclusive-or) operator, the algorithm can be reduced to two steps as shown in the solution above, so let’s have a look at how that’s done.

Why Does it Work?

On most platforms, the number of bits in a byte is 8, but the number of bytes in an int can vary. The position of the sign bit can therefore vary on different platforms, which is why the sole purpose of the first line of the code above is to extract the value of the sign bit. On an 8-bit computer it will simply compile to

int const mask = number >> 7;

and on a 64-bit machine it will compile to

int const mask = number >> 63;

The resulting value for mask is 1 for negative numbers and 0 for positive numbers, because the shift operation will insert zeros into the higher value bits to the left when shifting.

The second line of code adds the value of mask and then XOR’s the result with the mask, which essentially calculates the Two’s Complement, but only for negative numbers! This line looks somewhat cryptic, but it can be quite easily understood. Remember that the XOR operation results in a bit value of 1 if and only if the two operands are not equal, and a bit value of 0 if they are equal. This means that XOR’ing a single bit with a value of 1 has the effect of flipping the bit:

0 ^ 0 = 0
0 ^ 1 = 1   <--- left 0 turns into 1
1 ^ 0 = 1
1 ^ 1 = 0   <--- left 1 turns into 0

Now, we know that calculating the Two's Complement involves negating a number and adding 1 to it, and we also know that the sign bit is 1 only for negative numbers. Therefore, we can use the sign bit to negate an integer and add 1 to it if and only if it is negative. We can see that, for the decimal integer -122 the line will calculate the desired result:

100001100 + 1 = 100001101
100001101 ^ 1 = 011110010  <-- 122

For the positive integer 122 it has no effect:

011110010 + 0 = 011110010
011110010 ^ 0 = 011110010  <-- still 122

Things To Watch Out For

When using the Two's Complement to represent negative numbers, it is important to understand that there is one negative integer that cannot be converted into an absolute value. This integer is the most negative integer that can be represented with a given number of bits, because the range of positive numbers is one less than the range of negative numbers.

For example, 8 bits can be used to represent 256 distinct values (2 to the power of 8). If half of this range is used for negative numbers and one value for zero, then only 127 values are left for positive numbers, and hence the possible range of 8-bit values is -128 to 127.

In this particular case, the most negative number is -128, and its negation, 128, cannot be represented with just 8 bits. The unexpected result of the solution shown above will simply be the same number, and on 8-bit architectures it may look as follows:

10000000 + 1 = 10000001  <-- -128 + 1 = -127
10000001 ^ 1 = 10000000  <-- -128

This problem can be avoided by using a return type that has a larger range than the input type for the number to be converted, i.e. a return type of long int for input values of type int.

Related Resources

• Two's complement (Wikipedia)
• Why not enforce 2's complement in C++ (StackOverflow)
• size of int, long, etc (StackOverflow)