3
votes

Divisez deux entiers sans utiliser de multiplication, de division et d'opérateur mod en Java

J'écris un code qui trouve le quotient après avoir divisé deux nombres mais sans utiliser de multiplication, de division ou d'opérateur de mod.

Mon code

 if(fun_dividend<0 && fun_divisor<0){
        return count;
    }

Mon code passe le des cas de test comme dividende = -1, diviseur = 1 ou dividende = 1 et diviseur = -1. Mais il ne peut pas passer le cas de test comme dividende = --2147483648 et diviseur = -1. Cependant, j'ai une instruction if lorsque les deux entrées sont négatives.

  if(fun_dividend<0 && fun_divisor<0){
        return count;
    }

Lorsque mes entrées sont -2147483648 et -1, elle a renvoyé zéro. J'ai débogué mon code et j'ai découvert qu'il ne pouvait pas atteindre les instructions internes de la boucle while. Il suffit de vérifier la boucle while et de se terminer et d'exécuter

public int divide(int dividend, int divisor) {

    int diff=0,count=0;
    int fun_dividend=dividend;
    int fun_divisor=divisor;
    int abs_dividend=abs(dividend);
    int abs_divisor=abs(divisor);

    while(abs_dividend>=abs_divisor){
        diff=abs_dividend-abs_divisor;

        abs_dividend=diff;
        count++;

    }

    if(fun_dividend<0 && fun_divisor<0){
        return count;
    }
    else if(fun_divisor<0||fun_dividend<0) {
        return (-count);
    }

    return count;

}

C'est très évident, les deux entrées sont négatives, donc j'utilisais la fonction Math.abs pour les rendre positifs. Mais quand j'essaye de voir les valeurs des variables abs_dividend et abs_divisor, elles me montrent des valeurs négatives.

Un nombre entier maximum peut prendre un nombre à 9 chiffres. Alors, comment pourrais-je réussir ce cas de test? Selon ce cas de test, le dividende est un nombre à 10 chiffres qui n'est pas valide pour une plage d'entiers.

Selon le cas de test, la sortie que j'obtiens devrait être 2147483647.

Comment pourrait Je résous le bug?

Merci d'avance.

java function if-statement while-loop mod

0 commentaires

3 Réponses :

1
votes

Ran avec le débogueur et a trouvé que abs_dividend était -2147483648.

Ensuite, la comparaison dans while (abs_dividend> = abs_divisor) { est fausse et count n'est jamais incrémenté.

Il s'avère que l'explication se trouve dans le Javadoc pour Math.abs (int a) :

Notez que si l'argument est égal à la valeur de Integer.MIN_VALUE, la valeur int représentable la plus négative, le résultat est la même valeur, qui est négative.

Vraisemblablement, c'est parce que Integer.MAX_VALUE est 2147483647, il n'y a donc aucun moyen de représenter 2147483648 positif avec un int . (note: 2147483648 serait Integer.MAX_VALUE + 1 == Integer.MIN_VALUE )

0 commentaires

6
votes

Essayez d'utiliser la manipulation de bits pour cela comme suit:

public static int divideUsingBits(int dividend, int divisor) {
        // handle special cases
        if (divisor == 0)
            return Integer.MAX_VALUE;
        if (divisor == -1 && dividend == Integer.MIN_VALUE)
            return Integer.MAX_VALUE;

        // get positive values
        long pDividend = Math.abs((long) dividend);
        long pDivisor = Math.abs((long) divisor);

        int result = 0;
        while (pDividend >= pDivisor) {
            // calculate number of left shifts
            int numShift = 0;
            while (pDividend >= (pDivisor << numShift)) {
                numShift++;
            }

            // dividend minus the largest shifted divisor
            result += 1 << (numShift - 1);
            pDividend -= (pDivisor << (numShift - 1));
        }

        if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) {
            return result;
        } else {
            return -result;
        }
    }

1 commentaires

pourquoi cette ligne result + = 1 << (numShift - 1); et pas seulement result + = (numShift-1) ?

1
votes

Je résous le problème de cette façon. Donnez la préférence au type de données long sur int partout où il y a un risque de débordement lors du décalage à gauche. Gérez la casse au tout début pour éviter que les valeurs d'entrée ne soient modifiées dans le processus. Cet algorithme est basé sur la technique de division que nous utilisons à l'école.

public int divide(int AA, int BB) {
    // Edge case first.    
    if (BB == -1 && AA == Integer.MIN_VALUE){
        return Integer.MAX_VALUE;   // Very Special case, since 2^31 is not inside range while -2^31 is within range.
    }
    long B = BB;
    long A = AA;

    int sign = -1;
    if ((A<0 && B<0) || (A>0 && B>0)){
        sign = 1;
    }
    if (A < 0) A = A * -1;
    if (B < 0) B = B * -1;

    int ans = 0;
    long currPos = 1; // necessary to be long. Long is better for left shifting.
    while (A >= B){
        B <<= 1; currPos <<= 1;
    }
    B >>= 1; currPos >>= 1;
    while (currPos != 0){
        if (A >= B){
            A -= B;
            ans |= currPos;
        }
        B >>= 1; currPos >>= 1;
    }
    return ans*sign;
}

0 commentaires