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)
  66.     {
  67.         int bit = a.bit | b.bit;
  68.         for (State s : list)
  69.         {
  70.             if (s.bit == bit) return false;
  71.         }
  72.         list.add(new State(bit, "or", a, b));
  73.         return true;
  74.     }
  75.  
  76.     static boolean and(State a, State b, List<State> list)
  77.     {
  78.         int bit = a.bit & b.bit;
  79.         for (State s : list)
  80.         {
  81.             if (s.bit == bit) return false;
  82.         }
  83.         list.add(new State(bit, "and", a, b));
  84.         return true;
  85.     }
  86.  
  87.     static boolean not(State a, List<State> list)
  88.     {
  89.         int bit = a.bit ^ 0b11111111;
  90.         for (State s : list)
  91.         {
  92.             if (s.bit == bit) return false;
  93.         }
  94.         list.add(new State(bit, "not", a));
  95.         return true;
  96.     }
  97.  
  98.     static void combination(List<State> list)
  99.     {
  100.         int n = 1;
  101.         while (true)
  102.         {
  103.             int size = list.size();
  104.             for (int i = 0; i < size - 1; i++)
  105.             {
  106.                 State a = list.get(i);
  107.                 for (int j = n; j < size; j++)
  108.                 {
  109.                     and(a, list.get(j), list);
  110.                 }
  111.             }
  112.             for (int i = 0; i < size - 1; i++)
  113.             {
  114.                 State a = list.get(i);
  115.                 for (int j = n; j < size; j++)
  116.                 {
  117.                     or(a, list.get(j), list);
  118.                 }
  119.             }
  120.             if (list.size() == size) return;
  121.             n = size;
  122.         }
  123.     }
  124.  
  125.  
  126.     public static void main(String[] args)
  127.     {
  128.         State x = new State(0b00001111, "  x");
  129.         State y = new State(0b00110011, "  y");
  130.         State z = new State(0b01010101, "  z");
  131.         State notX = new State(0b11110000, "x'");
  132.         State notY = new State(0b11001100, "y'");
  133.         State notZ = new State(0b10101010, "z'");
  134.  
  135.         ArrayList<State> orand = new ArrayList<>(Arrays.asList(x, y, z));
  136.         combination(orand);
  137.  
  138.         for (int n1 = 0; n1 < orand.size(); n1++)
  139.         {
  140.             ArrayList<State> orandnot = new ArrayList<>(orand);
  141.             if (!not(orand.get(n1), orandnot)) continue;
  142.             combination(orandnot);
  143.  
  144.             for (int n2 = 0; n2 < orandnot.size(); n2++)
  145.             {
  146.                 ArrayList<State> result = new ArrayList<>(orandnot);
  147.                 if (!not(orandnot.get(n2), result)) continue;
  148.                 combination(result);
  149.  
  150.                 if (result.contains(notX) && result.contains(notY) && result.contains(notZ))
  151.                 {
  152.                     for (State s : result)
  153.                     {
  154.                         if (s.equals(notX)) notX = s;
  155.                         else if (s.equals(notY)) notY = s;
  156.                         else if (s.equals(notZ)) notZ = s;
  157.                     }
  158.  
  159.                     TreeSet<State> set = new TreeSet<>();
  160.                     notX.set(set);
  161.                     notY.set(set);
  162.                     notZ.set(set);
  163.                     int notCount = 0, orCount = 0, andCount = 0;
  164.                     for (State s : set)
  165.                     {
  166.                         if (s.type == "not")
  167.                         {
  168.                             s.name = String.format("N%02d", ++notCount);
  169.                             s.text = String.format("%s = not(%s)      : %s =~%s", s.name, s.parent[0].name, s.bit(), s.parent[0].bit());
  170.                         }
  171.                         else if (s.type == "or")
  172.                         {
  173.                             s.name = String.format("O%02d", ++orCount);
  174.                             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());
  175.                         }
  176.                         else if (s.type == "and")
  177.                         {
  178.                             s.name = String.format("A%02d", ++andCount);
  179.                             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());
  180.                         }
  181.                         else
  182.                         {
  183.                             s.name = s.type;
  184.                             s.text = String.format("%s: %s", s.name, s.bit());
  185.                         }
  186.                         System.out.println(s);
  187.                     }
  188.                     System.out.printf("x' = %s%n", notX.name);
  189.                     System.out.printf("y' = %s%n", notY.name);
  190.                     System.out.printf("z' = %s%n", notZ.name);
  191.                     System.out.printf("not=%d, or=%d, and=%d%n", notCount, orCount, andCount);
  192.                 }
  193.             }
  194.         }
  195.     }
  196. }
Success #stdin #stdout 7.45s 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/sVPIDp
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!