how to get absolute value of a number in java using bit manipulation

I want to implement a function to get the absolute value of a number in java: do nothing if it is positive, if it is negative, convert to positive.

I want to do this only using bit manipulations and no number comparators.

Please help

Solution

Well a negation:

-n

Is the same as the two's complement:

~n + 1

The problem is here you only want to negate if the value is < 0. You can find that out by using a logical shift to see if the MSB is set:

n >>> 31

A complement would be the same as an XOR with all 1's, something like (for a 4-bit integer):

~1010 == 1010 ^ 1111

And we can get a mask with the arithmetic right shift:

n >> 31

Absolute value says:

if n is < 0, negate it (take the complement and add 1 to it)
else, do nothing to it

So putting it together we can do the following:

static int abs(int n) {
    return (n ^ (n >> 31)) + (n >>> 31);
}

Which computes:

if n is < 0, XOR it with all 1's and add 1 to it
else, XOR it with all 0's and add 0 to it

I'm not sure there's an easy way to do it without the addition. Addition involves any number of carries, even for a simple increment.

For example 2 + 1 has no carry:

10 + 1 == 11

But 47 + 1 has 4 carries:

101111 + 1 == 110000

Doing the add and carry with bitwise/bit shifts would basically just be a loop unroll and pointless.

(Edit!)

Just to be silly, here is an increment and carry:

static int abs(int n) {
    int s = n >>> 31;
    n ^= n >> 31;

    int c;
    do {
        c = (n & s) << 1;
        n ^= s;
    } while((s = c) != 0);

    return n;
}

The way it works is it flips the first bit, then keeps flipping until it finds a 0. So then the job is just to unroll the loop. The loop body can be represented by a somewhat ridiculous compound one-liner.

static int abs(int n) {
    int s = n >>> 31;
    n ^= n >> 31;

    int c = (n & s) << 1;
    c = ((n ^= s) & (s = c)) << 1; // repeat this line 30 more times
    n ^= s;

    return n;
}

So there's an abs using only bitwise and bit shifts.

These aren't faster than Math.abs. Math.abs just returns n < 0 ? -n : n which is trivial. And actually the loop unroll totally sucks in comparison. Just a curiosity I guess. Here's my benchmark:

Math.abs: 4.627323150634766ns
shift/xor/add abs: 6.729459762573242ns
loop abs: 12.028789520263672ns
unrolled abs: 32.47122764587402ns
bit hacks abs: 6.380939483642578ns

(The bit hacks abs is the non-patented one shown here which is basically the same idea as mine except a little harder to understand.)