class ALU {

	public String integerDivision (String operand1, String operand2, int length) {
		
		String formattedOperand1 = complementLength(operand1, length);
		String formattedOperand2 = complementLength(operand2, length);
		
		if (formattedOperand2.indexOf("1")==-1){
			return "NaN";
		}
		
		String thatTwoRegisters = repeatedString(formattedOperand1.substring(0,1), length)+formattedOperand1;
		String minusOperand2 = negation(formattedOperand2);
		
		
		boolean isOverflow = false;
		boolean nextPlus = false; //indicates next op, true for plus and false for minus
		char Qn;
		//calculates Qn and judges if overflow
		if (isSignTheSame(formattedOperand1, formattedOperand2)){
			thatTwoRegisters = adder(thatTwoRegisters.substring(0,length), minusOperand2, '1', length).substring(1) + thatTwoRegisters.substring(length);
			if (isSignTheSame(thatTwoRegisters, formattedOperand2)){
				Qn = '1';
				nextPlus = false;
				isOverflow = true;
			}
			else{
				Qn = '0';
				nextPlus = true;
			}
		}else{
			thatTwoRegisters = adder(thatTwoRegisters.substring(0,length), formattedOperand2, '0',length).substring(1) + thatTwoRegisters.substring(length);
			if (isSignTheSame(thatTwoRegisters, formattedOperand2)){
				Qn = '1';
				nextPlus = false;
			}
			else{
				Qn = '0';
				isOverflow = true;
				nextPlus = true;
			}
		}
		
		thatTwoRegisters = thatTwoRegisters.substring(1)+Qn;
		
		//cycle
		for(int i=0;i<length;i++){
			if (!nextPlus){
				thatTwoRegisters =  adder(thatTwoRegisters.substring(0, length), minusOperand2, '1', length).substring(1) + thatTwoRegisters.substring(length);

			}else{
				thatTwoRegisters = adder(thatTwoRegisters.substring(0, length), formattedOperand2, '0', length).substring(1) + thatTwoRegisters.substring(length);
			}
			if (isSignTheSame(thatTwoRegisters, formattedOperand2)){
				Qn='1';
				nextPlus = false;
			}else{
				Qn='0';
				nextPlus = true;
			}
			if (i!=length-1){
				thatTwoRegisters = thatTwoRegisters.substring(1) + Qn;
			}

		}
		
		//cycle ends
		String left = thatTwoRegisters.substring(0,length);
		String result = thatTwoRegisters.substring(length+1)+Qn;

		
		if (!isSignTheSame(formattedOperand1, formattedOperand2)){
			result = oneAdder(result).substring(1);
		}

		
		if (!isSignTheSame(left, formattedOperand1)){
			if (isSignTheSame(formattedOperand1,formattedOperand2)){
				left = adder(left, formattedOperand2, '0', length).substring(1);
			}else{
				left = adder(left, minusOperand2, '1',length).substring(1);
			}
		}
		
		//handle left=operand2 -6/-3=2
		if (integerSubtraction(left, operand2, length).substring(1).equals(repeatedString("0", length))){
			left = repeatedString("0",length);
			result = oneAdder(result).substring(1);
		}
		
		//handle left=-operand2 -6/3=-2
		if (integerAddition(left, operand2, length).substring(1).equals(repeatedString("0", length))){
			left = repeatedString("0",length);
			result = integerAddition(result, repeatedString("1", length),length).substring(1);
		}
		
		isOverflow = isOverflow || (result.equals("1"+repeatedString("0", length-1)));
		
		
		return (isOverflow ? "1" : "0") + result+left;
	
	}

}