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

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

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