Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!weretis.net!feeder4.news.weretis.net!news.musoftware.de!wum.musoftware.de!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 22:28:52 +0200 Organization: albasani.net Lines: 68 Message-ID: References: <4e613b65$0$311$14726298@news.sunsite.dk> <_ZGdna1ucfWYH__TnZ2dnUVZ_oudnZ2d@earthlink.com> <4e655c24$0$308$14726298@news.sunsite.dk> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-15; format=flowed Content-Transfer-Encoding: 7bit X-Trace: news.albasani.net NiA3vLnEtVhLgM3/E7Rgd8BAjlbfHzpO7Zrq2jrWtnr9BAKoMKWKt29Me/l+mEaD9+PwnIItCYHJ+WXsFO6u0g== NNTP-Posting-Date: Tue, 6 Sep 2011 20:28:52 +0000 (UTC) Injection-Info: news.albasani.net; logging-data="6IB/7MsTJOs/nKPZ5r7Ev4kLs6jI9x1VN3rMh/K2BwYlUCE6TIMhAq50UtRx6KJiI7aNed3EqdHofioPXnx/LaW0ATgWHovqt26LxiPivd4o0s54ChlNEvK8GFI/Crfx"; mail-complaints-to="abuse@albasani.net" User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:6.0.1) Gecko/20110830 Firefox/6.0.1 SeaMonkey/2.3.1 In-Reply-To: Cancel-Lock: sha1:4yKUGqJUGc3eRgFH99U9LMjrdAY= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:7634 Jan Burse schrieb: >> - BigInteger is also not dependent for positive values on some >> two's complement, sign-plus-maginitude or one's complement etc.., >> since these presentation were invented for negative values. > ... > > import java.math.BigInteger; > public class BigIntegerTest { > public static void main(String[] args) { > BigInteger x = BigInteger.valueOf(3); > BigInteger y = BigInteger.valueOf(2); > System.out.println(x.or(y.not())); > } > } Well the above invalidates my claim to some extend. Since you produced an example where you get a negative number from bitwise ops on positive numbers. But from the context of my claim, it should of course also be clear that I exclude the not() operation. Since I have mentioned the not() operation many times a special to BigInteger. If you exclude the not() operation, you will stay in the positive domain. Also excluding the not() operation makes sense since you cannot directly translate an example that uses the not() from BigInteger to BitSet. You can translate the following special case (use a purely functional notation, although the BitSet call is in fact an inline modification of the first operand): BigInteger: and(x,not(y)) BitSet: andNot(x,y) But for the following operation, we don't find an equivalent in BitSet, since we would leave the positive integer domain, as you have shown: BigInteger: or(x,not(y)) BitSet: ?? So the Android advice is limited to the cases where you stay in the positive domain. And in this domain there is no performance penalty found in any representation schema that deals with negatives numbers, since we work with positive numbers only. And in the positive domain the same algorithm are usually used for BigInteger bitwise operation and for BitSet operations. Also in the Android code the same algorithm is used for BigInteger bitwise operations and for BitSet operations. I have quoted as an example the xor() code. But since the Android code internally uses C for the integer operations and Java for the bitwise operations in BigInteger, a copy operation is involved that copies from C to Java, before doing the bitwise operation. This copying is cached, and of course does not happen anymore after a couple of bitwise operations, since the operands are already cached, and the result as well. Bye P.S.: BigInteger has also an andNot(), which sends positive integers to positive integers, I do not exclude this operation in my claim.