0

I need to read in a couple of extremely large strings which are comprised of binary digits. These strings can be extremely large (up to 100,000 digits) which I need to store, be able to manipulate (flip bits) and add together. My first though was to split the string in to 8 character chunks, convert them to bytes and store them in an array. This would allow me to flip bits with relative ease given an index of the bit needed to be flipped, but with this approach I'm unsure how I would go about adding the entirety of the two values together.

Can anyone see a way of storing these values in a memory efficient manner which would allow me to be able to still be able to perform calculations on them?

EDIT: "add together" (concatenate? arithmetic addition?) - arithmetic addition

My problem is that in the hardest case I have two 100,000 bit numbers (stored in an array of 12,500 bytes). Storing and manually flipping bits isn't an issue, but I need the sum of both numbers and then to be able to find out what the xth bit of this is.

Martyn
  • 16,432
  • 24
  • 71
  • 104

2 Answers2

1

"Strings of binary digits" definitely sound like byte arrays to me. To "add" two such byte arrays together, you'd just allocate a new byte array which is big enough to hold everything, and copy the contents using System.arraycopy.

However that assumes each "string" is a multiple of 8 bits. If you want to "add" a string of 15 bits to another string of 15 bits, you'll need to do bit-shifting. Is that likely to be a problem for you? Depending on what operations you need, you may even want to just keep an object which knows about two byte arrays and can find an arbitrary bit in the logically joined "string".

Either way, byte[] is going to be the way forward - or possibly BitSet.

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • Thanks Jon, Bitset looks like the way forward. How could I efficiently add the two numbers together using bit-shifting? – Martyn Feb 04 '12 at 16:51
  • 1
    @Martyn: I'm not sure the best way of doing that with `BitSet` - with byte arrays, you'd need to iterate over every byte, shifting if necessary and OR-ing with the remainder from the previous byte (which would also have been shifted). It's going to be fiddly and not "simple blitting"-style efficiency, but it shouldn't be too bad. I suggest you draw out some samples on paper. – Jon Skeet Feb 04 '12 at 17:00
  • 2
    If you're adding the numbers, you may have more luck with `BigInteger`. – Louis Wasserman Feb 04 '12 at 18:01
0

What about

// Addition

byte[] resArr = new byte[byteArr1.length];

for (int i=0; i<byteArr1.length; i++)
{
    res = byteArr1[i]+byteArr2[i];
}

?

Is it something like this you are trying to do?

nijoakim
  • 930
  • 10
  • 25