Problem with bitwise implementation And problems in Java

Question

I am trying to solve a problem that basically involves the implementation of a logical AND between an input parameter.

The complexity of the problem is related to the size of the input parameters. To give a high level overview, I am trying to implement logic similar to

100 & 100 == 100 001 & 010 == 0 001 & 100 == 0 ..... 

The difficulty is that some of the input parameters can be 400 bits long. This is not a true binary numeric representation. It is rather a positional representation. The same input can be represented as

 100 = x1; (or) x100 011 = x2,3; (or) x011 001.......11 = x3,......450,451; 

So basically “x” is just a prefix with a value for it. This is an ACL system developed a long time ago, and I'm trying to implement a version of Java for it.

I could not find a data type in Java that could be used to represent a binary representation that is as huge as 400 bits. I can also use decimal representation [i.e. X2,3] and solve it too, but I could not think differently than going over the entire range of numbers and comparing it with another input parameter. Both input parameters can be normalized to the same presentation format [that is, binary or decimal].

Any suggestions (or) help in solving this problem?

Answer 1

You can use BitSet . It supports bitwise operations and should handle 400 bits well.

Here is an example:

 BitSet bs1 = new BitSet(); bs1.set(2); bs1.set(5); bs1.set(7); bs1.set(8); BitSet bs2 = new BitSet(); bs2.set(2); bs2.set(7); bs2.set(9); bs1.and(bs2); // Prints {2, 7} System.out.println(bs1); 

To x110101 line, you can do something like

 String acl = "x110101"; BitSet bs1 = new BitSet(); for (int i = 1; i < acl.length(); i++) if (acl.charAt(i) == '1') bs1.set(i); 

---

If you still don't like this approach, you can use Set<Integer> , which contains the indices of those. To define an “and” between two such sets, you simply do set1.retainAll(set2) .

Here is an example:

 Set<Integer> bs1 = new HashSet<Integer>(); bs1.add(2); bs1.add(5); bs1.add(7); bs1.add(8); Set<Integer> bs2 = new HashSet<Integer>(); bs2.add(2); bs2.add(7); bs2.add(9); bs1.retainAll(bs2); // Prints [2, 7] System.out.println(bs1); 

Answer 2

java.util.BitSet .

Answer 3

BigInteger should also work:

• the new BigInteger (binaryString, 2) should correctly parse the input
• BigInteger implements "and"
• use testBit (n) to access the bits