Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.dougwise.org!nntpfeed.proxad.net!proxad.net!feeder1-2.proxad.net!news.glorb.com!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 02 Sep 2011 15:35:01 -0500
Date: Fri, 02 Sep 2011 13:34:33 -0700
From: Patricia Shanahan <pats@acm.org>
User-Agent: Mozilla/5.0 (Windows NT 5.2; WOW64; rv:6.0) Gecko/20110812 Thunderbird/6.0
MIME-Version: 1.0
Newsgroups: comp.lang.java.programmer
Subject: Re: BitSet vs BigInteger (false Android doc)
References: <j3rbtv$d5g$1@news.albasani.net> <4e613b65$0$311$14726298@news.sunsite.dk>
In-Reply-To: <4e613b65$0$311$14726298@news.sunsite.dk>
Content-Type: text/plain; charset=ISO-8859-15; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <yJCdnamwfpVooPzTnZ2dnUVZ_umdnZ2d@earthlink.com>
Lines: 45
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 70.230.204.158
X-Trace: sv3-tWppgh1hWOqbDGOZOYSSNT9ZQR1IU4bGbfzLdg64WIjtTKnVOUPq5Lh/htLMa8ld/Tjb0p0er7Pg1lp!sE/AlVZp9xN1jrHZDG34l+4i41N/cXGczvtUKZhoHi/F6iBdDT/yewUGDX+8gSfu47tu9DgSK3QS!RIXXsgDk52ecfzYxmhpwbDn5i2oIIRZ5Dnv2RiEhPtgk5l0=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3007
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:7542

On 9/2/2011 1:23 PM, Arne Vajhøj wrote:
> On 9/2/2011 3:48 PM, Jan Burse wrote:
>> Just notice the following note on Android for
>> java.lang.BigInteger:
>>
>> Slow Two's Complement Bitwise Operations
>> This API includes operations for bitwise operations
>> in two's complement representation. Two's complement
>> is not the internal representation used by this
>> implementation, so such methods may be inefficient.
>> Use BitSet for high-performance bitwise operations
>> on arbitrarily-large sequences of bits.
>>
>> But why should be BitSet any faster than BigInteger? Both
>> BitSet and BigInteger don't use some sparse representation.
>> They just allocate an array, in the case of BitSet its a long
>> array, and in the case of BigInteger int array.
>>
>> The BigInteger sign does not slow down the process in any way.
>> Its just that the highest int of the BigInteger carries a sign,
>> which is arbirarily extended to the left. So BigInteger can
>> represent:
>>
>> ....1xxxxxx
>>
>> With an infinite sequence of 1's to the left. And then do
>> boolean operation. But there is practically no overhead
>> for that. But what I saw is that BitSet is not immutable,
>> so this could be a reason. But the two's complement is
>> not an issue, this is just rubbish.
>>
>> Right?
>
> 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.

Also, they have more freedom of action in implementing BitSet, because
it only needs to do the bit operations. BigInteger has to do the bit
operations in a way that is consistent with signed integer arithmetic.

Patricia