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

Question

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

Answer 1

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

Answer 2

you can turn a two's-compliment number positive or negative by taking it's logical negation

i = ~i; // i equals not i

You can use the Math.max() function to always get the positive

public static int abs(int i) {
    return Math.max(i,~i);
}

Answer 3

This depends on what type of number you are using. For an int, use

int sign = i >> 31;

This gets the sign bit, which is 0 for positive numbers, and 1 for negative numbers. For other primitive types, replace 31 with the number of bits used for the primitive minus 1.

You can then use that sign in your if statement.

if (sign == 1)
    i = ~i + 1;

Answer 4

I think you'll find that this little ditty is what you're looking for:

int abs(int v) {
    int mask = v >> Integer.SIZE - 1;

    return v + mask ^ mask;
}

It's based on Bit Twiddling Hacks absolute value equation and uses no comparison operations. If you aren't allowed to use addition, then (v ^ mask) - mask is an alternative. The value of this function is fairly questionable; since it's nearly as clear as the implementation of Math.abs and it's only marginally faster (at least on a i7):

1. v + mask ^ mask: 2.0844380704220384 abs/ns
2. (v ^ mask) - mask: 2.0819764093030244 abs/ns
3. Math.abs: 2.2636355843860656 abs/ns

Here's a test that proves that it works over the entire range of integers (the test runs in less than 2 minutes on an i7 processor under Java 7 update 51):

package test;

import org.hamcrest.core.Is;
import org.junit.Assert;
import org.junit.Test;

public class AbsTest {

    @Test
    public void test() {
        long processedCount = 0L;
        long numberOfIntegers = 1L << Integer.SIZE; //4294967296L
        int value;

        for (value = Integer.MIN_VALUE; processedCount < numberOfIntegers; value++) {
            Assert.assertEquals((long) abs(value), (long) StrictMath.abs(value));
            if (processedCount % 1_000_000L == 0L) {
                System.out.print(".");
            }
            processedCount++;
        }
        System.out.println();
        Assert.assertThat(processedCount, Is.is(numberOfIntegers));
        Assert.assertThat(value - 1, Is.is(Integer.MAX_VALUE));
    }

    private static int abs(int v) {
        int mask = v >> Integer.SIZE - 1;

        return v + mask ^ mask;
    }

}

Answer 5

This problem can be broken down into 2 simple steps:

1. If >= 0 then just return the number.

2. If smaller than 0 (ie. negative), then flip the first bit that indicates that the number is negative. This can easily be done with an XOR operation with -1 and the number; Then simply add +1 to deal with the offset (signed integers start at -1 not 0).

public static int absolute(int a) {
    if (a >= 0) {
        return a;
    } else  {
        return (a ^ -1) + 1;
    }
}