def extend(p: Long): Long = {
    var ones=0
    for (i<-0 to 62){
      var c = (p >> i) & 1
      if(c == 1) ones += 1
    }
   if(ones%2==0) p&(0<<63)
   else p|(1<<63)
  }