5

I am looking for a way to add two BitSet. Should i go to the basics of binary number and perform XOR and AND operation over BitSet. As basic says here- Half Adder

Will this be efficient?

ravi
  • 6,140
  • 18
  • 77
  • 154
  • @stefanbachert no.... not at all. actually i am improving my programming skills. so just playing with `bitset` class – ravi Mar 30 '12 at 15:51

2 Answers2

4

No, it wouldn't be efficient, because you wouldn't know the carry for bit N until you've processed all bits through N-1. This is the problem solved by carry look-ahead adders in hardware.

There is no way to implement addition of BitSets in a way that does not involve examining all their bits one-by-one in the worst case. An alternative strategy depends a lot on your specific requirements: if you mutate your bit sets a lot, you may want to roll your own, based on Sun's Oracle's implementation. You can shamelessly copy borrow their code, and add an implementation of add that operates on the "guts" of the BitSet, stored as long[] bits. You'll need to be very careful dealing with overflows (remember, all numbers in Java are signed), but otherwise it should be rather straightforward.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • 1
    you mix up efficient and effective. You mean in truth "effective" ("it works correctly") when you say "efficient" ("it works fast/with less resources") – stefan bachert Mar 30 '12 at 15:33
  • @stefanbachert I really do mean "efficient", as in "works fast". You can use the scheme from the OP as a base of a correct implementation, but it would require combining carry flags from half-addres with results of additions multiple times, until you have no new carry flags; this may take `N` in the worst case, where `N` is the number of bits in the larger of the two numbers. – Sergey Kalinichenko Mar 30 '12 at 15:38
  • Let me try. if i can manage the carry then it would be best, otherwise i have to convert it to integer/long. – ravi Mar 30 '12 at 16:21
  • 1
    @RaviJoshi You do not need to try it in code, just think about it: mentally set all bits from 0 to 1000 in one `BitSet`, and bit zero in the other `BitSet`. Now add the two together. You'll get a carry in bit one, zero in bit zero, and ones all the way to 1000 in the remaining bits. Now apply the carry, and get zero in bits zero and one, a carry in bit two, and ones all the way to 1000. It is clear that you'd need to repeat it 1000 times to get to the end, which is grossly inefficient. – Sergey Kalinichenko Mar 30 '12 at 16:26
  • @RaviJoshi (I don't believe I'm saying this) you can use reflection to "fish out" the `bits` array from the `BitSet` (oh no! I said it!) This is a certified hack, so do it at your own risk. I needed to do it once to serialize lots of large `BitSet`s in a reasonably successful commercial product, and it worked; however, I wrote lots of unit tests around it, and I used to run them every time we switched to the new release of Java. It's a horrible, horrible thing, so do not do it unless you absolutely must. – Sergey Kalinichenko Mar 30 '12 at 16:32
  • @dasblinkenlight:I don't have knowledge about using reflection in java. However currently i am thinking to [convert](http://stackoverflow.com/a/2473719/1175065) both bitset to integer/long then perform addition. would this be fast enough ? if not than can you please elaborate your concept more. – ravi Mar 30 '12 at 17:59
  • @RaviJoshi This conversion takes one bit at a time, so it is rather slow. If you are OK using it, you might as well do addition one bit at a time: it will be equally slow. – Sergey Kalinichenko Mar 30 '12 at 19:23
  • @RaviJoshi Did you try downloading sources for `BitSet` from [here](http://fuseyism.com/classpath/doc/java/util/BitSet-source.html), for example, modifying the package name to that of your company, and compiling it as your own? This should be very easy, it's a self-contained piece of code. This will let you skip the conversion altogether, which will save tremendous amounts of time. – Sergey Kalinichenko Mar 30 '12 at 19:24
  • @dasblinkenlight: I already have the complete JDK1.6 source but where is the addition code of `BitSet`? Currently I am using `BigInteger` to add two `BitSet` of size large. Firstly i am converting `Bitset` into `StringBuilder` in the following manner- ` a is a BitSet StringBuilder sb1 = new StringBuilder(n); for (int j = 0; j < n; j++) { int bit = a.get(n - j - 1) ? 1 : 0; sb1 = sb1.append(bit); } //sb2 is defined in the same way for BitSet b BigInteger c = new BigInteger(sb1.toString(), 2) .add(new BigInteger(sb2.toString(), 2)); ` Too slow. :( – ravi Mar 30 '12 at 20:08
  • 1
    @RaviJoshi You need to write that addition code yourself. Use the `bits` array of `BitSet` in the same way the [`setAdd` method](http://developer.classpath.org/doc/java/math/BigInteger-source.html) of `BigInteger` uses its array called `words`. Note that `BigInteger`'s array is `int`, not `long`, so they have easier time dealing with overflow. Your logic would be somewhat more involved, but it's doable. – Sergey Kalinichenko Mar 30 '12 at 20:27
1

The most efficient way would be to convert both bitsets to numbers and just add them

stefan bachert
  • 9,413
  • 4
  • 33
  • 40
  • 1
    As by unrolling a `BitSet` to a non-negative `BigInteger`? – Mike Samuel Mar 30 '12 at 15:30
  • yes, however, I would to use int or long when the bits are limited to that – stefan bachert Mar 30 '12 at 15:32
  • @stefanbachert: What if that `bitset` is large? how to use BigInteger on that case? – ravi Mar 30 '12 at 18:55
  • this is very theoretically. In the end we are talking about adding two numbers. A long has 63 bit plus sign. A long is capable to count in 2ns steps since big bang. Anything we are talking is far from a realistic practical use – stefan bachert Mar 30 '12 at 19:05