Re: BitSet vs BigInteger (false Android doc)
On 9/2/2011 3:48 PM, Jan Burse wrote:
Dear All,
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? [...]
Question: Are Android's BitSet and BigInteger similar to Java's?
If not, read no further. But if so:
- Flipping a bit in a BitSet flips it _in situ_, modifying the
value of the original BitSet.
- Flipping a bit in a BigInteger produces a brand-new BigInteger,
leaving the original BigInteger untouched.
So: Flip a thousand bits one by one in a BitSet and you make a
thousand changes to the value of that one BitSet (perhaps the
underlying array gets reallocated sometimes). Flip the same thousand
bits in a BigInteger and you create a thousand new BigInteger instances
with their thousand new underlying arrays. In a crude timing test on
my machine, the difference was noticeable: Flipping a thousand bits a
thousand times took 437 ms with BigInteger, 16 ms with BitSet. YMMV.
--
Eric Sosman
esosman@ieee-dot-org.invalid