arrondi rapide nombre à virgule fixe

Question

Disons que je traite mon entier comme s'il avait 4 bits de fraction. Et maintenant 0 est zéro, 16 est un, 32 est deux, et ainsi de suite. En arrondissant, les nombres dans l'intervalle [-7, 7] deviennent 0, [8, 23] deviennent 16.

Mon code est le suivant :

std::int64_t my_round(std::int64_t n) {
    auto q = n / 16;
    auto r = n % 16;
    if (r >= 0) {
        if (r >= 8) {
            ++q;
        }
    } else {
        if (r <= -8) {
            --q;
        }
    }
    return q * 16;
}

C'est beaucoup de code pour une tâche aussi simple. Je me demande s'il existe un moyen plus rapide de le faire. J'ai seulement besoin de supporter les entiers signés en 64 bits.

Éditer : Il y avait un commentaire (je ne me souviens pas qui l'a fait) qui suggérait d'ajouter 15 et de masquer les bits inférieurs. Cela n'a pas fonctionné. Mais avec quelques essais et erreurs, je suis arrivé à ceci.

std::int64_t my_round2(std::int64_t n) {
    if (n >= 0) {
        n += 8;
    }
    else {
        n += 7;
    }
  return n & (~15ll);
}

Je n'en ai aucune idée. Mais my_round2 semble donner le même résultat que my_round et est 20 fois plus rapide. S'il y a un moyen de supprimer la branche, ce serait beaucoup mieux.

Answer 1

Avec

return (n + 8 + (n>>63)) & (~15ll);

on peut raser la branche de my_round2() et assurer la symétrie originale à zéro. L'idée est que signed type >> (sizeof(signed type) * 8 - 1) est de -1 pour les valeurs négatives et de 0 pour les valeurs positives.

Clang est capable de produire du code sans branche pour l'original. my_round2() mais c'est toujours une instruction de plus que la routine proposée ici. Avec arm64, les économies sont encore plus grandes.

Answer 2

Que diriez-vous de quelque chose comme

std::int64_t my_round2(std::int64_t n) {
    int sign = n >= 0 ? 1 : -1;
    n = sign > 0 ? n: -n;
    int64_t n1 = (n + 8) >>4;
    n1<<= 4;
    return n1 * sign;
}

Il y a toujours le problème de débordement.

Answer 3

Tant que votre représentation d'un entier est à complément à deux (ce qui est pratiquement requis par d'autres éléments de la norme C11), il suffit d'ajouter 8 et de masquer les bits inférieurs :

int64_t my_round2(int64_t n) {
    return (n + 8) & ~UINT64_C(15);
}