How can I get log value of a negative value?

Question

I have a function of the following table.

input: e	output: 1 << e
0	1
1	2
...	...
31	-2147483648

static int value(int exponent) {
    return 1 << exponent;
}

Now, how can I get the exponent from a value?

I tried the following code and it fails for the last entry of -2147483648.

int exponent(int value) {
    return (int) (Math.log(value) / Math.log(2)); // -> NaN / Math.log(2)
}

And I managed to fix it like this.

int exponent(int value) {
    if (value == Integer.MIN_VALUE) {
       return (int) (Math.log(value - 1) / Math.log(2)) + 1;
    }
    return (int) (Math.log(value) / Math.log(2));
}

Is there any better/proper way to do this?

Answer 1

You can use Integer.numberOfLeadingZeros for that. According to its JavaDoc:

Note that this method is closely related to the logarithm base 2. For all positive int values x:

floor(log2(x)) = 31 - numberOfLeadingZeros(x)
ceil(log2(x)) = 32 - numberOfLeadingZeros(x - 1)

To implement your exponent method, simply copy what the JavaDoc suggests:

int exponent(int value) {
    return 31 - Integer.numberOfLeadingZeros(value);
}

Note that this also works for negative numbers in your case, even though the logarithm is not defined for non-positive numbers: For all negative numbers, the left-most bit will be 1 due to their representation in the two's complement. Therefore, for any negative value, Integer.numberOfLeadingZeros returns 0, and hence your exponent method calculates 31.

Also note, that if value == 0, then exponent returns -1 which is a case you might want to take care of. For example, you could throw an IllegalArgumentException since the logarithm is undefined for 0.

Answer 2

Using Integer.numberOfLeadingZeros() as Alex R has suggested in their answer would perfectly fine for positive input, but for any negative number

31 - Integer.numberOfLeadingZeros(value)

would be evaluated as 31 because the very first bit of every negative number is 1.

This result (exponent of 31) makes sense for -2147483648 since 2^31 = 2147483648 (as Alex R stated in their answer), but not for -1, -16, -256, etc.

To get the correct result for a negative input, you need to work with the absolute value of the given input.

In order to treat the case when the given is Integer.MIN_VALUE (which has no positive equivalent in int type because Integer.MAX_VALUE is less by one) without additional checks, you can use long.

Here's one of the way to implement it using bitwise logic:

public static int exponent(int value) {
    if (value == 0) throw new IllegalArgumentException();
    
    long mod = Math.abs((long) value);
    
    long mask = 1;
    int exp = 31;
    
    while ((mask << exp & mod) == 0) { // until left bit is not 1, decrement the exponent
        exp--;
    }
    
    return exp;
}

Simple demonstration:

public static void main(String[] args) {
    System.out.println("value: 1" + "\texponent: " + exponent(1));
    System.out.println("value: 2" + "\texponent: " + exponent(2));
    System.out.println("value: 8" + "\texponent: " + exponent(8));
    System.out.println("value: 32" + "\texponent: " + exponent(32));
    System.out.println("value: 64" + "\texponent: " + exponent(64));
    System.out.println("value: 256" + "\texponent: " + exponent(256));
    System.out.println("value: " + Integer.MAX_VALUE + "\texponent: " + exponent(Integer.MAX_VALUE));
    
    System.out.println("value: -1" + "\texponent: " + exponent(-1));
    System.out.println("value: -2" + "\texponent: " + exponent(-2));
    System.out.println("value: -8" + "\texponent: " + exponent(-8));
    System.out.println("value: -32" + "\texponent: " + exponent(-32));
    System.out.println("value: -64" + "\texponent: " + exponent(-64));
    System.out.println("value: -256" + "\texponent: " + exponent(-256));
    System.out.println("value: " + Integer.MIN_VALUE + "\texponent: " + exponent(Integer.MIN_VALUE));
}

Output:

value: 1    exponent: 0
value: 2    exponent: 1
value: 8    exponent: 3
value: 32   exponent: 5
value: 64   exponent: 6
value: 256  exponent: 8
value: 2147483647   exponent: 30

value: -1   exponent: 0
value: -2   exponent: 1
value: -8   exponent: 3
value: -32  exponent: 5
value: -64  exponent: 6
value: -256 exponent: 8
value: -2147483648  exponent: 31