Convert a String to array of bits

Question

I would like to convert a String consisting of 0's and 1's to an array of bits.
The String is of length ~30000 and is sparse (mostly 0s, few 1s)
For example, given a string
"00000000100000000010000100000000001000"
I would like to convert it to an array of bits which will store
[00000000100000000010000100000000001000]

I am thinking of using BitSet or OpenBitSet Is there a better way? The use case is to perform logical OR efficiently.

I am thinking along these lines

final OpenBitSet logicalOrResult = new OpenBitSet(); 
for (final String line : lines) {

   final OpenBitSet myBitArray = new OpenBitSet(); 
   int pos = 0;
   for (final char c : str.toCharArray()) {
         myBitArray.set(pos) = c;
         pos++;
   }
   logicalOrResult.or(myBitArray);
}

@StevenA.Lowe It's either a good question or a bad one. Why do you care if it's homework? — Anubian Noob
– Anubian Noob, Commented Oct 2, 2014 at 1:31
@AnubianNoob: if it's homework, and I tell the OP the answer, then they've learned nothing. see meta.stackexchange.com/questions/18242/… for semi-official policy — Steven A. Lowe
– Steven A. Lowe, Commented Oct 2, 2014 at 1:33
@Tad: tell us what you've tried instead of asking for a "better" answer; otherwise this is likely to get closed rapidly as a homework or unclear question — Steven A. Lowe
– Steven A. Lowe, Commented Oct 2, 2014 at 1:34
@StevenA.Lowe But a post "looks like homework..." is really not constructive. — Anubian Noob
– Anubian Noob, Commented Oct 2, 2014 at 1:37

Boann · Accepted Answer · 2014-10-02 01:45:24Z

2

BigInteger can parse it and store it, and do bitwise operations:

BigInteger x = new BigInteger(bitString, 2);
BigInteger y = new BigInteger(otherBitString, 2);
x = x.or(y);
System.out.println(x.toString(2));

answered Oct 2, 2014 at 1:45

Boann

50.3k16 gold badges125 silver badges153 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Tad Over a year ago

do you know whether there are any benchmarks between BigInteger and OpenBitSet and BitSet (or any other library) for performing logical OR?

Boann Over a year ago

@Tad I do not know, but you can easily compare them by doing the benchmarks within the intended application.

misberner · Accepted Answer · 2014-10-02 02:14:14Z

1

A BitSet ranging over values between 0 and 30000 requires a long array of size less than 500, so you can assume that BitSet.or (or the respective OpenBitSet method) will be sufficiently fast, despite the sparsity. It looks like OpenBitSet has better performance than BitSet, but apart from this it doesn't really matter which you use, both will implement or efficiently. However, be sure to pass the length of the String to the (Open)BitSet constructor to avoid reallocations of the internal long array during construction!

If your strings are much longer and your sparsity is extreme, you could also consider storing them as a sorted list of Integers (or ints, if you use a library like Trove), representing the indices which contain a 1. A bitwise or can be implemented in a merge(sort)-like fashion, which is quite efficient (time O(n + m), where n, m are the numbers of ones in each string). I suspect that in your scenario it will be slower than the BitSet approach though.

answered Oct 2, 2014 at 2:14

misberner

3,70823 silver badges19 bronze badges

2 Comments

Tad Over a year ago

my BitSet will range over values 1 and 0 - not 0 and 30000. Is this what you mean?

misberner Over a year ago

No. Your BitSet represents a set of integers between 0 and some upper limit. E.g., the bitset 01001101 represents the set {0, 2, 3, 6} - the set of indices set to 1. This is also what constitutes the toString() representation of a BitSet. Since your strings are of length ~30000, the corresponding set of 1-indices ranges over values between 0 and 30000.

Anubian Noob · Accepted Answer · 2014-10-02 01:40:48Z

0

You can iterate through each character:

boolean[] bits = new boolean[str.length];

for (int i=0;i<str.length;i++) {
    if (str.charAt(i).equals("1")
        bits[i] = true;
    else if (str.charAt(i).equals("0")
        bits[i] = false;
}

If you want to be memory efficient, you could try RLE (Run Length Encoding).

answered Oct 2, 2014 at 1:40

Anubian Noob

13.6k6 gold badges55 silver badges76 bronze badges

1 Comment

Tad Over a year ago

I like this approach but I have read in stackoverflow.com/questions/383551/… that using BitSet has a better optimization than an array of booleans. I was also considering RLE, which would be great since my array is sparse, but I am not sure how to do logical OR on compressed array - I guess I would need to decompress it first, unless I am missing something.

Collectives™ on Stack Overflow

Convert a String to array of bits

3 Answers 3

2 Comments

2 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related