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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

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 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
TheDarkKnight
Guest

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?

Ronny
Guest

Better:

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