Modulos non signés: approche alternative?

Question

J'ai besoin d'optimiser cette fonction vraiment minuscule mais embêtante.

 unsigned umod(int a, unsigned b)
{
    while(a < 0)
        a += b;

    return a % b;
}
 

Avant de crier "Vous n'avez pas besoin de l'optimiser", gardez à l'esprit que cette fonction est appelée à 50% de la durée de vie du programme, car elle est appelée 21495808 fois pour le plus petit test de référence.

La fonction est déjà en cours de création par le compilateur, veuillez donc ne pas proposer d'ajouter le mot clé inline .

Answer 1

Cela évite le bouclage:

 int tmp = a % b;
if (tmp < 0) tmp += b;
 

Notez que a et b doivent être signés.

Answer 2

Cela devrait le faire:

 unsigned umod(int a, unsigned b)
{
    if (a < 0)
    {
        unsigned r = (-a % b);
        if (r)
            return b - r;
        else
            return 0;
    }
    else
        return a % b;
}
 

Testé pour correspondre à l'original. La limite est que a > INT_MIN sur les machines complémentaires 2s.

Answer 3

Utilisation du ~ :)

 unsigned umod(int a, unsigned b)
{
    if (a<0) return b-1-~a%b;
    return a%b;
}
 

Le % a une priorité plus élevée que -

Si vous pouvez retourner b au lieu de 0 lorsque -a est un multiple de b, vous pouvez enregistrer des opérations

 unsigned umod(int a, unsigned b)
{
    if (a<0) return b - (-a % b);
    return a%b;
}
 

version légèrement golfée :)

 unsigned umod(int a, unsigned b)
{
return(a<0)?b-(-a%b):a%b;
}
 

Voici l'assemblage résultant

 1    .globl umod3
2       .type   umod3, @function
3    umod3:
4    .LFB3:
5       .cfi_startproc
6       testl   %edi, %edi
7       js      .L18
8       movl    %edi, %eax
9       xorl    %edx, %edx
10      divl    %esi
11      movl    %edx, %eax
12      ret
13      .p2align 4,,10
14      .p2align 3
15   .L18:
16      movl    %edi, %eax
17      xorl    %edx, %edx
18      negl    %eax
19      divl    %esi
20      subl    %edx, %esi
21      movl    %esi, %edx
22      movl    %edx, %eax
23      ret
 

Answer 4

Étant donné que la version en boucle semble être assez rapide, essayons d'éliminer la division :)

 unsigned umod(int a, unsigned b){
    while(a>0)a-=b;
    while(a<0)a+=b;
    return a;
}
 

Answer 5

Édition portable, toujours avec une seule division, sans branchement et sans multiplication:

 unsigned umod(int a, unsigned b) {
    int rem = a % (int) b;
    return rem + (-(rem < 0) & b);
}