Given an integer, compute its absolute value (abs) without branching

We can use the expression ((n + mask) ^ mask) where mask is (n >> 31) (assuming 32 bit storage for integers) to compute the absolute value of n. The mask (n >> 31) will be evaluated to 0 for positive numbers and -1 for negative numbers. For instance,

00000110 (n = 6)

00000000 (mask = 0)

00000110 ^ (n + mask)

00000000 (mask)

~~~~~~~~

00000110 abs(n)

11111010 (n = -6)

11111111 (mask = -1)

11111001 ^ (n + mask)

11111111 (mask)

~~~~~~~~

00000110 abs(n)

##### How this works?

For positive integer n, mask will be 0 and (n + 0) ^ 0 = n. So, no trick behind this one.

Now for a **negative integer n**, mask will be -1 and (n – 1) ^ -1 = n. But how?

We know that in 2’s complement notation, a negative number is represented by flipping the bits of its positive counterpart and adding 1 to it. Now to get the positive counterpart of a negative number, we subtract 1 from it and flip its bits.

-n = ~n + 1

n = ~(-n – 1)

Here also we are doing the same. We subtract mask (-1) from the given negative number and flip its bits by taking its XOR with the mask.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> #include <bitset> using namespace std; // main function int main() { int n = -6; int const mask = n >> sizeof(int) * 8 - 1; cout << "n (" << n << ") in binary is " << bitset<8>(n) << endl; cout << "mask (" << mask << ") in binary is " << bitset<8>(mask); cout << "\n(n + mask) in binary is " << bitset<8>(n + mask); cout << "\n\nabs(" << n << ") is " << ((n + mask) ^ mask); return 0; } |

`Output:`

n (-6) in binary is 11111010

mask (-1) in binary is 11111111

(n + mask) in binary is 11111001

abs(-6) is 6

##### Another solution –

If branching was allowed, we could have directly use the expression ((n >> 31) & 1) ? (~n + 1) : n to return the absolute value of n. But we can easily modify the expression to **((n >> 31) & (~n + 1)) | ((~n >> 31) & n)**. Now it will return the absolute value of n and it doesn’t even use ternary operator. As discussed earlier, the mask (n >> 31) will be evaluated to 0 (zero) for positive numbers and -1 (non-zero) for negative numbers. Similarly the mask (~n >> 31) will be evaluated to 0 (zero) for negative numbers and -1 (non-zero) for positive numbers.

Now for a positive number, ((n >> 31) & (~n + 1)) will be all 0’s and ((~n >> 31) & n) will equal to n and for a negative number, ((n >> 31) & (~n + 1)) will equal to n and ((~n >> 31) & n) will be all 0’s. So in either case, one side of OR operator is 0 and OR operator will return the non-zero value, which happens to be the absolute value of n.

For other solutions to this problem that do not use binary operators, one can refer here.

**Read More –**

Bit Hacks – Part 1 (Basic)

Bit Hacks – Part 2 (Playing with k’th bit)

Bit Hacks – Part 3 (Playing with rightmost set bit of a number)

Bit Hacks – Part 4 (Playing with letters of English alphabet)

Bit Hacks – Part 6 (Random Problems)

**References: **https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Hey,

Thanks a lot for such an amazing content.

However I am unable to understand how mask becomes -1 in case of negative numbers.

Going by your example: n = -6 = 1111 1010

mask = n >> 31 = 1111 1010 >> 31 = 0000 0000 (coz in right shift operator leading spaces are to be filled with 0s same as that in left shift operator)

How this becomes -1. I am sure I am missing something here?

Hello,

(-6) = (11111111111111111111111111111010)

In case of negative numbers, the MSB is always 1 and leading spaces will be filled with 1s (not 0s) in right shift operator. So

1111 1010 >> 31 is 1111 1111, which is binary representation of -1

Again thank you so much.

I got my mistake. I though that on right shift, leading bits are always set to 0 irrespective of the sign of n. Thanks for correcting me here.

A related question: For left shift operator, are the trailing digits always filled with zeros or if this is different for negative numbers? Please answer.

For left shift operator, the trailing digits are always filled with 0’s for both positive and negative numbers.

Better:It is exactly what’s done in two’s complement negation.