Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to add two BitSet

Tags:

java

bitset

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?

like image 479
Ravi Joshi Avatar asked Mar 30 '12 15:03

Ravi Joshi


People also ask

How many ways are there for constructing a BitSet?

Explanation: There are three ways of constructing a bitset. Direct construction, using integer number and using binary string.

How do you add bits in CPP?

Add two unsigned numbers using bits in C++. An unsigned number represented as a stream of bits is written in binary form. The binary form of 54 is 110110. Adding two numbers using bits, we will add their binary form using the binary addition logic. Explanation − 10101 + 11011 = 110000.

How big can a BitSet be?

Java BitSet size() method The maximum element in the set is the size - 1st element. The default size of the bit set is 64-bit space. If the bit is set at index larger than the current BitSet size, it increases its bit space in the multiplication of 64*n, where n starts from 1, 2, 3, so on.


1 Answers

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.

like image 82
Sergey Kalinichenko Avatar answered Oct 10 '22 05:10

Sergey Kalinichenko