# Bit Hacks – Part 5 (Find absolute value of an integer without branching)

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)
~~~~~~~~
00000110                     abs(n)

11111010                     (n = -6)
11111111                     (mask = -1)

11111001   ^                 (n + 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++

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.     (1 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest
TheDarkKnight

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? Guest

Better:

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