Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #7544

Re: BitSet vs BigInteger (false Android doc)

Show all headers | View raw

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

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-02 21:48 +0200
  Re: BitSet vs BigInteger (false Android doc) Arne Vajhøj <arne@vajhoej.dk> - 2011-09-02 16:23 -0400
    Re: BitSet vs BigInteger (false Android doc) Patricia Shanahan <pats@acm.org> - 2011-09-02 13:34 -0700
      Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-02 22:51 +0200
        Re: BitSet vs BigInteger (false Android doc) Patricia Shanahan <pats@acm.org> - 2011-09-02 18:58 -0700
          Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-03 20:15 +0200
            Re: BitSet vs BigInteger (false Android doc) Patricia Shanahan <pats@acm.org> - 2011-09-03 12:37 -0700
              Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-03 22:46 +0200
                Re: BitSet vs BigInteger (false Android doc) Patricia Shanahan <pats@acm.org> - 2011-09-03 16:32 -0700
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-04 02:58 +0200
                Re: BitSet vs BigInteger (false Android doc) Arne Vajhøj <arne@vajhoej.dk> - 2011-09-05 19:32 -0400
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-06 08:58 +0200
                Re: BitSet vs BigInteger (false Android doc) Lew <lewbloch@gmail.com> - 2011-09-06 00:41 -0700
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-06 11:57 +0200
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-06 12:12 +0200
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-06 12:44 +0200
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-06 12:02 +0200
                Re: BitSet vs BigInteger (false Android doc) Patricia Shanahan <pats@acm.org> - 2011-09-06 13:38 -0700
                Re: BitSet vs BigInteger (false Android doc) Patricia Shanahan <pats@acm.org> - 2011-09-06 10:33 -0700
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-06 22:28 +0200
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-06 22:41 +0200
                Re: BitSet vs BigInteger (false Android doc) Patricia Shanahan <pats@acm.org> - 2011-09-06 14:34 -0700
                Re: BitSet vs BigInteger (false Android doc) Lew <lewbloch@gmail.com> - 2011-09-06 14:51 -0700
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-07 00:33 +0200
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-07 00:40 +0200
            Re: BitSet vs BigInteger (false Android doc) Arne Vajhøj <arne@vajhoej.dk> - 2011-09-05 19:26 -0400
      Re: BitSet vs BigInteger (false Android doc) Robert Klemme <shortcutter@googlemail.com> - 2011-09-03 17:01 +0200
    Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-02 22:49 +0200
      Re: BitSet vs BigInteger (false Android doc) Gene Wirchenko <genew@ocis.net> - 2011-09-02 14:48 -0700
  Re: BitSet vs BigInteger (false Android doc) Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-03 13:54 -0400

csiph-web