Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.albasani.net!.POSTED!not-for-mail
From: Jan Burse <janburse@fastmail.fm>
Newsgroups: comp.lang.java.programmer
Subject: Re: BitSet vs BigInteger (false Android doc)
Date: Fri, 02 Sep 2011 22:49:20 +0200
Organization: albasani.net
Lines: 74
Message-ID: <j3rfgp$lh6$1@news.albasani.net>
References: <j3rbtv$d5g$1@news.albasani.net> <4e613b65$0$311$14726298@news.sunsite.dk>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-15; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: news.albasani.net c58G5H6XhQl+csSPvFeh/X03ONZ/ONg3ZRAPGiU2o7FfD2t3Svq2iDXH0F7k5o7aUeju+sCDUQ/TvM+BUV6VtQ==
NNTP-Posting-Date: Fri, 2 Sep 2011 20:49:29 +0000 (UTC)
Injection-Info: news.albasani.net; logging-data="YTKRRyjfboobw3ENro/3HHV/3fa1l+wrmkbDqFmureBb4j/VxM5YgHmFtQajzqEJmu73pKd0s0Xvt10mvAh9MkWDTAjMaWN2T19/VW2iePQIOTJDBvPlULKMfHzuEu2p"; mail-complaints-to="abuse@albasani.net"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:6.0.1) Gecko/20110830 Firefox/6.0.1 SeaMonkey/2.3.1
In-Reply-To: <4e613b65$0$311$14726298@news.sunsite.dk>
Cancel-Lock: sha1:rMy9/2mJPkXbMIgoevKJ2vpLn44=
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:7544

Arne Vajhøj schrieb:
>
> Not necessarily.
>
> If the internal representation does not match
> the external representations then some operations could
> be expensive due to the conversion between representations
> and/or complications for the operation itself.
>
> Arne

In the present case the internal representation
is basically the same for BitSet and BigInteger.
The operations are also the same. Here is the
code for the logical xor in BigInteger and BitSet:

    BigInteger:

     public BigInteger xor(BigInteger val) {
	int[] result = new int[Math.max(intLength(), val.intLength())];
	for (int i=0; i<result.length; i++)
	    result[i] = (getInt(result.length-i-1)
			 ^ val.getInt(result.length-i-1));

	return valueOf(result);
     }

    BitSet:

     public void xor(BitSet set) {
         int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);

         if (wordsInUse < set.wordsInUse) {
             ensureCapacity(set.wordsInUse);
             wordsInUse = set.wordsInUse;
         }

	// Perform logical XOR on words in common
         for (int i = 0; i < wordsInCommon; i++)
	    words[i] ^= set.words[i];

	// Copy any remaining words
	if (wordsInCommon < set.wordsInUse)
	    System.arraycopy(set.words, wordsInCommon,
			     words, wordsInCommon,
			     set.wordsInUse - wordsInCommon);

         recalculateWordsInUse();
	checkInvariants();
     }


The immutable vs. mutable difference is seen in the signature
of the methods, and the use of ^ vs ^=.

There is a little speed-up in BitSet that the xor has only
to be applied to the min and not to the max array lengths
as is the case for BigInteger. But in the end the result will
also occupy max of the array lengths.

But if I need immutable BitSet I will also need to make a
copy first. So the Android comment is not true, there is
no intrinsic dependency on some representation, since both
representations are the same on the common domain of
positive integers:
http://developer.android.com/reference/java/math/BigInteger.html

That BitSet corresponds to the domain of positive integers
can be seen by the fact that BitSet has no not() operation,
whereby BigInteger has.

Bye