29. Divide Two Integers.txt

//Ñàìîå êðóòîå ðåøåíèå áåç long. 
//Êàê êîä ðàáîòàåò ÿ ïîíÿë, íî ãëîáàëüíóþ èäåþ ÿ íå ðàçîáðàë.
int divide(int dividend, int divisor) {
	//Îòäåëüíûå ñëó÷àè
	if (dividend == INT_MIN && divisor == -1) return INT_MAX;
	if (dividend == INT_MIN && divisor == 1) return INT_MIN;
	if (dividend == INT_MIN && divisor == INT_MIN) return 1;
	if (divisor == INT_MIN) return 0;

	//sign íóæíà äëÿ îïðåäåëåíèÿ çíàêà ôèíàëüíîãî îòâåòà(+ èëè -)
	//Çäåñü èñïîëüçóþòñÿ ïîáèòûâûå îïåðàöèè. Ó âñåõ îòðèöàòåëüíûõ ÷èñåë ñàìûé áîëüøîé áèò áóäåò åäèíè÷íûì.
	//1 << 31 ýòî -2147483648 = INT_MIN.  äâîè÷íîì âèäå ýòî -10000000000000000000000000000000. Òî åñòü âñå 0 êðîìå ñòàðøåãî áèòà(îí 1).
	//& Âîçâðàùàåò 1, åñëè îáà ÷èñëà ðàâíû 1. Åñëè îáà ÷èñëà îòðèöàòåëüíû, òî ó îáîèõ ÷èñåë â äâîè÷íîì âèäå ñòàðøèé áèò áóäåò = 1. Îïåðàöèÿ & âûäàñò true.
	//^ Âîçâðàùàåò 1, åñëè òîëüêî îäèíî èç ÷èñåë ðàâíî 1. Ò.î. Åñëè ÒÎËÜÊÎ ÎÄÍÀ ïåðåìåííàÿ áóäåò îòðèöàòåëüíîé, sign áóäåò = true, èíà÷å false;
	bool sign = (dividend & (1 << 31)) ^ (divisor & (1 << 31));
	int ans = 0; //Îòâåò
	if (divisor < 0) divisor = -divisor;//Ìåíÿåì çíàê äåëèòåëÿ åñëè îí îòðèöàòåëüíûé
	if (dividend == INT_MIN) {//Åñëè äåëèìîå == ïðåäåëüíîìó ìèíèìàëüíîìó çíà÷åíèþ int
		dividend += divisor; //Ïðèáàâëÿåì ê äåëèìîìó äåëèòåëü. Èçáåãàåì ïåðåïîëíåíèå int
		ans++;//Îòâåò = 1
	}

	if (dividend < 0) dividend = -dividend;//Ìåíÿåì çíàê äåëèìîãî åñëè îí îòðèöàòåëüíûé

	while (true) {
		int x = 0;
		//Óâåë÷èâàåì õ ïîêà äåëèòåëü áîëüøå íóëÿ è íå áîëüøå äåëèìîãî
		//Äåëèòåëü << x ìîæåò ïåðåïîëíèòüñÿ (êîãäà îí ñòàíåò îòðèöàòåëüíûì)
		// divisor << x could overflow (when it becomes negative)
		while ((divisor << x) > 0 && dividend >= (divisor << x)) x++;

		if (!x) break;//Åñëè x = 0
		ans += 1 << (x - 1);//Äîáàâëÿåì îòâåò
		dividend -= divisor << (x - 1);//Óìåíüøàåì äåëèìîå
	}

	return sign ? -ans : ans; // Åñëè sign true òî âîçâðàùàåì -ans èíà÷å âîçâðàùàåì ans.
}



//Ðåøåíèå ñ ëîíãàìè.
class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }
        long dvd = labs(dividend), dvs = labs(divisor), ans = 0;
        int sign = dividend > 0 ^ divisor > 0 ? -1 : 1;
        while (dvd >= dvs) {
            long temp = dvs, m = 1;
            while (temp << 1 <= dvd) {
                temp <<= 1;
                m <<= 1;
            }
            dvd -= temp;
            ans += m;
        }
        return sign * ans;
    }
};

//Ìîé êîä. Âîçíèêàåò îøèáêà ïåðåïîëíåíèÿ int. Ðåøàåòñÿ îíà ïðèñâîåíèåì long âåñòî int è çàäà÷åé ìíîæåñòâà if, íî â ýòîé çàäà÷å ýòî íå ïðàâèëüíî.
//Äà òóò ãëàâíàÿ ïðîáëåìà íå äåëåíèå, à ïåðåïîëíåíèå int.
class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }
        long answer = 0;
        if (dividend < 0 && divisor < 0) {
            while (dividend <= divisor) {
                dividend -= divisor;
                answer++;
            }
        }
        else if (dividend < 0) {
            divisor = 0 - divisor;
            while (dividend <= divisor) {
                dividend -= divisor;
                answer++;
            }
            answer = 0 - answer;
        }
        else if (divisor < 0) {
            divisor = 0 - divisor;
            while (dividend >= divisor) {
                dividend -= divisor;
                answer++;
            }
            answer = 0 - answer;
        }
        else {
            while (dividend >= divisor) {
                dividend -= divisor;
                answer++;
            }
        }
        if (answer > 2147483647)
            return 2147483647;
        if (answer < -2147483648)
            return -2147483648;
        else
            return answer;
    }
};