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)
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++

Download   Run Code

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

Notify of
avatar
Sort by:   newest | oldest | most voted
TheDarkKnight
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?

wpDiscuz