import java.util.concurrent.CyclicBarrier;
import java.lang.Thread;
import java.util.concurrent.BrokenBarrierException;

public class PPfix extends Thread{	
  int nr;
  int tot;
  int[] sa;
  CyclicBarrier b;
  
  public PPfix(int nr, int[] sa,int tot,CyclicBarrier b){
    this.nr=nr;
    this.sa=sa;
    this.tot=tot;
    this.b=b;
  }

  public void run(){
    try{
      int runs=(int)Math.ceil((Math.log((double)tot)/Math.log(2.0)));
      for(int i=0;i<runs;i++){
        int old = sa[nr];
        b.await();
        int ind = nr+(1<<i);
        if(ind<tot) sa[ind]+=old;
        b.await();
      }
    }catch(InterruptedException e){
      e.printStackTrace();
    }catch(BrokenBarrierException e){
      e.printStackTrace();
    }
    if(nr==0)System.out.println("sum is "+sa[tot-1]);
  }
  
  public static void main(String[] args){
    if(args.length<1){
      System.out.println("Please supply nr of threads to run as an argument");
      System.exit(1);
    }
    int nrThreads = Integer.parseInt(args[0]);
    int[] shared = new int[nrThreads];
    for(int i=0;i<nrThreads;i++) shared[i]=i;
    CyclicBarrier b = new CyclicBarrier(nrThreads);
    for(int i=0;i<nrThreads;i++){
      PPfix p = new PPfix(i,shared,nrThreads,b);
      p.start();	
    }
  }
}