Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!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: Sat, 03 Sep 2011 18:33:26 -0500
Date: Sat, 03 Sep 2011 16:32:56 -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> <yJCdnamwfpVooPzTnZ2dnUVZ_umdnZ2d@earthlink.com> <j3rflb$lh6$2@news.albasani.net> <KOmdnWyhfYV_FPzTnZ2dnUVZ_s-dnZ2d@earthlink.com> <j3tqr7$vp8$1@news.albasani.net> <_ZGdna1ucfWYH__TnZ2dnUVZ_oudnZ2d@earthlink.com> <j3u3me$k4s$1@news.albasani.net>
In-Reply-To: <j3u3me$k4s$1@news.albasani.net>
Content-Type: text/plain; charset=ISO-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <YOydnZpW5enbJP_TnZ2dnUVZ_hKdnZ2d@earthlink.com>
Lines: 23
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 70.230.204.158
X-Trace: sv3-WNWfjIOYP+T/dtKIAtWeioeYQ+u6HespnQ73lXi9hmyT75mV8Ze50578QYQP/xj7k4BqfD7gVpUw7Na!hLOD0csaGodY5l5DNZGW5qxOPOkAaRc6RQnEkn54CKRCEJ65ngy2UbN00R2yL8CTckdAAAg/8ERm!DDPlHuKPh382/7FkR8UUvmfB9TFzSsDig9lNweO2aVi25aw=
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: 2361
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:7554

On 9/3/2011 1:46 PM, Jan Burse wrote:
> 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.
>
...

Could you explain why you are assuming 1's complement rather than
sign-and-magnitude?

Any of 2's complement, 1's complement, and sign-and-magnitude *could* be
used to implement BigInteger. The Android note you quoted eliminates 2's
complement, but does not say which is actually used.

Patricia