Thanks for pointing to the BigInteger implementation on Android!

Patricia Shanahan schrieb:

> It uses a NativeBN implementation, which appears from various comments

> and fields to be sign-and-magnitude based, not 2's complement. The bit

> manipulation methods use a method prepareJavaRepresentation that I think

> converts to 2's complement.
I don't see how the 1's complement influences the BigInteger performance

when we compare with BitSet. BitSet can only represent what corresponds

to positive numbers in BigInteger.

The prepareJavaRepresentation will only do an array copy, if the java

reprentation is not already cached. And then for example for xor

the fast route will be taken since we have two positive numbers:

static BigInteger xorPositive(BigInteger longer, BigInteger

shorter) {

// PRE: longer and shorter are positive;

// PRE: longer has at least as many digits as shorter

int resLength = longer.numberLength;

int[] resDigits = new int[resLength];

int i = Math.min(longer.getFirstNonzeroDigit(), shorter

.getFirstNonzeroDigit());

for (; i < shorter.numberLength; i++) {

resDigits[i] = longer.digits[i] ^ shorter.digits[i];

}

for (; i < longer.numberLength; i++) {

resDigits[i] = longer.digits[i];

}

return new BigInteger(1, resLength, resDigits);

}

http://www.java2s.com/Open-Source/An...gical.java.htm
Actually the code for negative numbers xor in 1's complement looks

really horrible. But this doesn't mean that it has an inherent

different complexity order.

If I remember well then we have -x = ~x + 1. So there is a potential

carry/borrow. This doesn't change much the loops. In fact you

might compare the not() in 1's complement and 2's complement. The

not() is much faster in 1's complement representation (with 2's

complement semantics).

But still I don't think that the Android comment covers the current

state of affairs. Since it explicitly refers to BitSet, and BitSet

and BigInteger are the same on the common domain of positive integers.

And now seeing Logical, there is a new argument against the comment.

Bit operations on 1's complement need not change the complexity

order.

Bye