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

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

Using expression `(n+mask)^mask`

The idea is to use the expression (n+mask)^mask for computing the absolute value of n, where mask is n >> 31 (assuming 32–bit storage for integers). 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 does it works?

For positive integer n, the mask will be 0 and (n + 0) ^ 0 = n. So, no trick behind this one. For a negative integer n, the 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, subtract 1 from it and flip its bits. i.e.,

-n = ~n + 1
n = ~(-n – 1)

The idea is same here – we subtract a mask -1 from the given negative number and flip its bits by taking its bitwise XOR with the mask. Following is the C++, Java, and Python program that demonstrates the idea:

C++

#include <iostream>

#include <bitset>

using namespace std;

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) << endl;

cout << "(n + mask) in binary is " << bitset<8>(n + mask) << endl;

cout << "abs(" << n << ") is " << ((n + mask) ^ mask) << endl;

return 0;

}

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

Java

class Main

{

public static void main(String[] args)

{

int n = -6;

final int mask = n >> Integer.SIZE * 8 - 1;

System.out.println("n (" + n + ") in binary is " + Integer.toBinaryString(n));

System.out.println("mask (" + mask + ") in binary is " +

Integer.toBinaryString(mask));

System.out.println("n + mask (" + n + mask + ") in binary is " +

Integer.toBinaryString(n + mask));

System.out.println("abs(" + n + ") is " + ((n + mask) ^ mask));

}

Download Run Code

Output:

n (-6) in binary is 11111111111111111111111111111010
mask (-1) in binary is 11111111111111111111111111111111
n + mask (-6-1) in binary is 11111111111111111111111111111001
abs(-6) is 6

Python

if __name__ == '__main__':

SIZE = 32

n = -6

mask = n >> SIZE * 8 - 1

print(f'n {n} in binary is', bin(n))

print(f'mask {mask} in binary is', bin(mask))

print(f'n + mask {n + mask} in binary is', bin(n + mask))

print(f'abs({n}) is', (n + mask) ^ mask)

Download Run Code

Output:

n -6 in binary is -0b110
mask -1 in binary is -0b1
n + mask -7 in binary is -0b111
abs(-6) is 6

Alternate Solution

If branching is allowed, we could have directly used the expression ((n >> 31) & 1) ? (~n + 1) : n to return the absolute value of n.

Since branching is not allowed, we can easily modify the above expression to ((n >> 31) & (~n + 1)) | ((~n >> 31) & n) which returns the absolute value of n without using the ternary operator. As discussed earlier, the mask n >> 31 is evaluated to 0 (zero) for positive numbers and -1 (non-zero) for negative numbers. Similarly, the mask ~n >> 31 is 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 be equal to n, and for a negative number, (n >> 31) & (~n + 1) will be equal to n and (~n >> 31) & n will be all 0's. So, in either case, one side of the OR operator is 0, and the OR operator will return the non-zero value, which happens to be the absolute value of n.

Also See:

Bit Hacks – Part 1 (Basic)
Bit Hacks – Part 2 (Playing with k’th bit)
Bit Hacks – Part 3 (Playing with the rightmost set bit of a number)
Bit Hacks – Part 4 (Playing with letters of the English alphabet)

Reference:

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

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

Using expression (n+mask)^mask

How does it works?

C++

Java

Python

Alternate Solution

Using expression `(n+mask)^mask`