fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.     static int idCount = 0;
  11.  
  12.     static class State implements Comparable<State>
  13.     {
  14.         final int id = idCount++;
  15.         final int bit;
  16.         final State[] parent;
  17.         String type;
  18.         String name;
  19.         String text;
  20.  
  21.         State(int bit, String s, State... parent)
  22.         {
  23.             this.bit = bit;
  24.             this.type = s;
  25.             this.parent = parent;
  26.         }
  27.  
  28.         @Override
  29.         public String toString()
  30.         {
  31.             return text;
  32.         }
  33.  
  34.         @Override
  35.         public int compareTo(State o)
  36.         {
  37.             return Integer.compare(id, o.id);
  38.         }
  39.  
  40.         @Override
  41.         public boolean equals(Object o)
  42.         {
  43.             return o instanceof State & ((State) o).bit == bit;
  44.         }
  45.  
  46.         @Override
  47.         public int hashCode()
  48.         {
  49.             return bit;
  50.         }
  51.  
  52.         String bit()
  53.         {
  54.             return Integer.toBinaryString(bit | 0b100000000).substring(1);
  55.         }
  56.  
  57.         private void set(Set<State> set)
  58.         {
  59.             set.add(this);
  60.             for (State s : parent)
  61.                 s.set(set);
  62.         }
  63.     }
  64.  
  65.     static boolean or(State a, State b, List<State> list, BitSet bitset)
  66.     {
  67.         int bit = a.bit | b.bit;
  68.         if (bitset.get(bit)) return false;
  69.         list.add(new State(bit, "or", a, b));
  70.         bitset.set(bit);
  71.         return true;
  72.     }
  73.  
  74.     static boolean and(State a, State b, List<State> list, BitSet bitset)
  75.     {
  76.         int bit = a.bit & b.bit;
  77.         if (bitset.get(bit)) return false;
  78.         list.add(new State(bit, "and", a, b));
  79.         bitset.set(bit);
  80.         return true;
  81.     }
  82.  
  83.     static boolean not(State a, List<State> list, BitSet bitset)
  84.     {
  85.         int bit = a.bit ^ 0b11111111;
  86.         if (bitset.get(bit)) return false;
  87.         list.add(new State(bit, "not", a));
  88.         bitset.set(bit);
  89.         return true;
  90.     }
  91.  
  92.     static void combination(List<State> list, BitSet bitset)
  93.     {
  94.         int n = 1;
  95.         while (true)
  96.         {
  97.             int size = list.size();
  98.             for (int i = 0; i < size - 1; i++)
  99.             {
  100.                 for (int j = Math.max(n, i + 1); j < size; j++)
  101.                 {
  102.                     and(list.get(i), list.get(j), list, bitset);
  103.                 }
  104.             }
  105.             for (int i = 0; i < size - 1; i++)
  106.             {
  107.                 for (int j = Math.max(n, i + 1); j < size; j++)
  108.                 {
  109.                     or(list.get(i), list.get(j), list, bitset);
  110.                 }
  111.             }
  112.             if (list.size() == size) return;
  113.             n = size;
  114.         }
  115.     }
  116.  
  117.  
  118.     public static void main(String[] args)
  119.     {
  120.         State x = new State(0b00001111, "  x");
  121.         State y = new State(0b00110011, "  y");
  122.         State z = new State(0b01010101, "  z");
  123.         State notX = new State(0b11110000, "x'");
  124.         State notY = new State(0b11001100, "y'");
  125.         State notZ = new State(0b10101010, "z'");
  126.  
  127.         ArrayList<State> orand = new ArrayList<>(Arrays.asList(x, y, z));
  128.         BitSet orandSet = new BitSet();
  129.         orandSet.set(x.bit);
  130.         orandSet.set(y.bit);
  131.         orandSet.set(z.bit);
  132.         combination(orand, orandSet);
  133.  
  134.         for (int n1 = 0; n1 < orand.size(); n1++)
  135.         {
  136.             ArrayList<State> orandnot = new ArrayList<>(orand);
  137.             BitSet orandnotSet = (BitSet) orandSet.clone();
  138.             if (!not(orand.get(n1), orandnot, orandnotSet)) continue;
  139.             combination(orandnot, orandnotSet);
  140.  
  141.             for (int n2 = n1 + 1; n2 < orandnot.size(); n2++)
  142.             {
  143.                 ArrayList<State> result = new ArrayList<>(orandnot);
  144.                 BitSet resultSet = (BitSet) orandnotSet.clone();
  145.                 if (!not(orandnot.get(n2), result, resultSet)) continue;
  146.                 combination(result, resultSet);
  147.  
  148.                 if (result.contains(notX) && result.contains(notY) && result.contains(notZ))
  149.                 {
  150.                     for (State s : result)
  151.                     {
  152.                         if (s.equals(notX)) notX = s;
  153.                         else if (s.equals(notY)) notY = s;
  154.                         else if (s.equals(notZ)) notZ = s;
  155.                     }
  156.  
  157.                     TreeSet<State> set = new TreeSet<>();
  158.                     notX.set(set);
  159.                     notY.set(set);
  160.                     notZ.set(set);
  161.                     int notCount = 0, orCount = 0, andCount = 0;
  162.                     for (State s : set)
  163.                     {
  164.                         if (s.type == "not")
  165.                         {
  166.                             s.name = String.format("N%02d", ++notCount);
  167.                             s.text = String.format("%s = not(%s)      : %s =~%s", s.name, s.parent[0].name, s.bit(), s.parent[0].bit());
  168.                         }
  169.                         else if (s.type == "or")
  170.                         {
  171.                             s.name = String.format("O%02d", ++orCount);
  172.                             s.text = String.format("%s =  or(%s, %s) : %s = %s | %s", s.name, s.parent[0].name, s.parent[1].name, s.bit(), s.parent[0].bit(), s.parent[1].bit());
  173.                         }
  174.                         else if (s.type == "and")
  175.                         {
  176.                             s.name = String.format("A%02d", ++andCount);
  177.                             s.text = String.format("%s = and(%s, %s) : %s = %s & %s", s.name, s.parent[0].name, s.parent[1].name, s.bit(), s.parent[0].bit(), s.parent[1].bit());
  178.                         }
  179.                         else
  180.                         {
  181.                             s.name = s.type;
  182.                             s.text = String.format("%s: %s", s.name, s.bit());
  183.                         }
  184.                         System.out.println(s);
  185.                     }
  186.                     System.out.printf("x' = %s%n", notX.name);
  187.                     System.out.printf("y' = %s%n", notY.name);
  188.                     System.out.printf("z' = %s%n", notZ.name);
  189.                     System.out.printf("not=%d, or=%d, and=%d%n", notCount, orCount, andCount);
  190.                 }
  191.             }
  192.         }
  193.     }
  194. }
Success #stdin #stdout 0.36s 320576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
  x: 00001111
  y: 00110011
  z: 01010101
A01 = and(  x,   y) : 00000011 = 00001111 & 00110011
A02 = and(  x,   z) : 00000101 = 00001111 & 01010101
A03 = and(  y,   z) : 00010001 = 00110011 & 01010101
O01 =  or(  x,   y) : 00111111 = 00001111 | 00110011
O02 =  or(  x,   z) : 01011111 = 00001111 | 01010101
O03 =  or(  y,   z) : 01110111 = 00110011 | 01010101
A04 = and(  x, A03) : 00000001 = 00001111 & 00010001
A05 = and(O02, O03) : 01010111 = 01011111 & 01110111
O04 =  or(  x, O03) : 01111111 = 00001111 | 01110111
A06 = and(O01, A05) : 00010111 = 00111111 & 01010111
N01 = not(A06)      : 11101000 =~00010111
A07 = and(O01, N01) : 00101000 = 00111111 & 11101000
A08 = and(O02, N01) : 01001000 = 01011111 & 11101000
A09 = and(O03, N01) : 01100000 = 01110111 & 11101000
O05 =  or(A01, N01) : 11101011 = 00000011 | 11101000
O06 =  or(A02, N01) : 11101101 = 00000101 | 11101000
O07 =  or(A03, N01) : 11111001 = 00010001 | 11101000
O08 =  or(A04, N01) : 11101001 = 00000001 | 11101000
A10 = and(O04, O08) : 01101001 = 01111111 & 11101001
N02 = not(A10)      : 10010110 =~01101001
O09 =  or(A07, N02) : 10111110 = 00101000 | 10010110
O10 =  or(A08, N02) : 11011110 = 01001000 | 10010110
O11 =  or(A09, N02) : 11110110 = 01100000 | 10010110
A11 = and(O05, O09) : 10101010 = 11101011 & 10111110
A12 = and(O06, O10) : 11001100 = 11101101 & 11011110
A13 = and(O07, O11) : 11110000 = 11111001 & 11110110
x' = A13
y' = A12
z' = A11
not=2, or=11, and=13
https://ideone.com/l0txFu
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!