code: public static long gcd(long x, long y) {
  		if(x < 0) x = -x;
  		if(y < 0) y = -y;
  		if(x < y) {
  			long temp = x;
  			x = y;
  			y = temp;
  		}
  		long gcd = 1;
  		while(y > 1) {
  			if((x & 1) == 0) {
  				if((y & 1) == 0) {
  					gcd <<= 1;
  					x >>= 1;
  					y >>= 1;
  				} else {
  					x >>= 1;
  				}
  			} else {
  				if((y & 1) == 0) {
  					y >>= 1;
  				} else {
  					x = (x - y) >> 1;
  				}
  			}
  			if(x < y) {
  				long temp = x;
  				x = y;
  				y = temp;
  			}
  		}
  		return y == 1 ? gcd : gcd * x;
  	}
docs: greatest common divisor