Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!nx02.iad01.newshosting.com!newshosting.com!news-out.readnews.com!transit3.readnews.com!postnews.google.com!news3.google.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Robert Klemme Newsgroups: comp.lang.java.programmer Subject: Re: BitSet vs BigInteger (false Android doc) Date: Sat, 03 Sep 2011 17:01:29 +0200 Lines: 60 Message-ID: <9cetqfFgg1U1@mid.individual.net> References: <4e613b65$0$311$14726298@news.sunsite.dk> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: quoted-printable X-Trace: individual.net 6L8HIxm7SexOO3VQMtaUAQ3UrQSvw44dUxILZ47xewo+hwdkM= Cancel-Lock: sha1:HGQ7QGar5JKBVZFNQVnOiXXIfuc= User-Agent: Mozilla/5.0 (Windows NT 6.0; WOW64; rv:6.0.1) Gecko/20110830 Thunderbird/6.0.1 In-Reply-To: Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:7549 On 02.09.2011 22:34, Patricia Shanahan wrote: > On 9/2/2011 1:23 PM, Arne Vajh=F8j 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. And there's more freedom to change the implementation at some point in=20 the future (or for another platform). BitSet is geared towards bit=20 operations while BigInteger is geared to math. So any changes done to=20 any of the two classes will keep the respective purpose of the class in=20 mind while they might neglect the other purpose which just comes as an=20 convenient add on. Kind regards robert --=20 remember.guy do |as, often| as.you_can - without end http://blog.rubybestpractices.com/