Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.albasani.net!.POSTED!not-for-mail From: Jan Burse Newsgroups: comp.lang.java.programmer Subject: Re: BitSet vs BigInteger (false Android doc) Date: Tue, 06 Sep 2011 11:57:28 +0200 Organization: albasani.net Lines: 52 Message-ID: References: <4e613b65$0$311$14726298@news.sunsite.dk> <_ZGdna1ucfWYH__TnZ2dnUVZ_oudnZ2d@earthlink.com> <4e655c24$0$308$14726298@news.sunsite.dk> <826a6f26-c540-4ee9-a0c6-1cf77f20d765@glegroupsg2000goo.googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: news.albasani.net H09zcc7/go8Y28T2J8TmcRHOItuBfehNlROSn1RgR8GUDzhdJaaaKmBXfpA5Q2ILPUEWYlVdWB2IDIK4os4T1Q== NNTP-Posting-Date: Tue, 6 Sep 2011 09:57:29 +0000 (UTC) Injection-Info: news.albasani.net; logging-data="f2iWCZFhcaHaCNKuy2tCZAMVcGZIual/bNM6kBSNV2yMk3L2sgKAVXRZwI96GNa0JfQT8Qt4MmnWFfh5c4GNmSNu7F0JAhuRo2MtkhgcpQmuegW4p6WX5d9V+PnwXvI1"; mail-complaints-to="abuse@albasani.net" User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6; rv:6.0.1) Gecko/20110830 Firefox/6.0.1 SeaMonkey/2.3.1 In-Reply-To: <826a6f26-c540-4ee9-a0c6-1cf77f20d765@glegroupsg2000goo.googlegroups.com> Cancel-Lock: sha1:eAnkhi2CNcugNPH2HQXtJQdtxxw= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:7616 Lew schrieb: > Also, BitSet does indeed have a "not" operation, which it calls 'flip()'. Sorry, but flip() is not the same as not(). Just compare the signatures: flip: Domain x Nat -> Domain flip(x,n) := xor(x,2^n) not: Domain -> Domain$ not(x) := xor(x,-1) This is really where the bitwise operations of BigInteger differentiate from the bitwise operations of BitSet. BitSet does only know a potentially infinitely extended sign bit of zero. So all the values seen as bits are: ...0xxxxxxx So when you do a BitSet operation between two operands of BitSet, then the shorter operand is extended so that both sizes match, before the operation is done (not necessary for all operation). And this extension works by padding with 0. In BigInteger we can represent two different bitset patterns. Namely the either a zero extended indefinitely, for positive numbers, or a one extended indefinitely, for negative numbers. So all the values in BigInteger seen as bits are: ...0xxxxxxx or ...1xxxxxxx The BigInteger operations have two pad eiter with 0 or with 1, depending on the sign of the given operand. The not() is not available in BitSet because the -1 is not available in BitSet. But what concerns the Android comment. It is false because two's complement is not relevant when we compare BitSet and BigInteger, because two's complement is one way to represent a negative number: ...1xxxxxxx And implicitly the Android comment is also false, since it implies that two's complement is the only way to represent negative numbers and it is also false, since it implies that some of negative number representations have a negative complexity impact on negative number bitwise operations. Bye