Quel est le moyen le plus rapide pour implémenter la carte signée à non signée r (x) = 2x-1 si x> 0 et r (x) = 2x autrement

Le mappage des entiers signés à des entiers non signés peut être fait en utilisant des techniques courantes comme Two's complément. Malheureusement, ils échouent à mapper de petits entiers négatifs à de petits nombres. Pour les algorithmes de compression, nous voulons souvent préserver autant que possible la valeur absolue des nombres: les petits nombres négatifs et positifs doivent être mappés sur de petits nombres.Quel est le moyen le plus rapide pour implémenter la carte signée à non signée r (x) = 2x-1 si x> 0 et r (x) = 2x autrement

Une carte populaire est r (x) = -2x-1 si x < 0 et r (x) = 2x si x> = 0. (Un semblable est r (x) = -2x si x < = 0 et 2x + 1 si x> 0.)

Implémentée naïvement, cette carte est relativement lente. Certainement beaucoup plus lent que de simplement lancer des entiers signés à des entiers non signés (ce qui applique silencieusement le complément de deux).

Quel est le moyen le plus rapide?

Source

2010-08-24 Daniel Lemire

x> 0 au lieu de x ≥ 0 right ? – kennytm

Je ne pense pas qu'il soit logique de poser une question de performance sans spécifier de matériel (et un compilateur, pour les solutions en C). –

@KennyTM: En supposant que l'entrée signée est un complément à 2, elle doit être 'x> = 0' (pas' x> 0' comme le dit le questionneur). Sinon, MIN_INT et 0 sont tous deux mappés à 0, ce qui contredit la "bijection". –

silently applies Two's complement, oui, sur la plupart des plates-formes mondern c'est juste un nop le compilateur interprète simplement vos données différemment. Donc c'est vraiment difficile à battre.

Pour votre comparision il serait bon si vous fournir quelques repères ...

Si je ne me trompe 2 * abs(x) + signbit peut être fait avec un décalage vers la gauche cyclique des bits. Donc si votre plate-forme a une telle instruction, cela devrait être facile à implémenter avec l'assembleur en ligne et ne devrait aboutir qu'à une seule instruction à la fin.

Edit: je me suis trompé, cette chose simple ne fonctionnerait avec signe et la valeur représentation des nombres négatifs.

Pour le complément à deux, vous devez annuler le résultat de la rotation si l'entrée a été négative. Quelque chose comme

inline uint64_t rotateL(uint64_t x) { 
    asm ("rolq %0" : "=r" (x) : "r" (x)); 
    return x; 
} 

inline uint64_t value(uint64_t x) { 
    uint64_t ret = rotateL(x); 
    return (ret % UINT64_C(2)) 
    ? -ret 
    : ret; 
}

J'ai regardé dans l'assembleur qu'il a produit par gcc. On dirait tout à fait bon, a seulement 5 instructions

rolq %rax 
movq %rax, %rdx 
negq %rdx 
testb $1, %al 
cmovne %rdx, %rax

Source

2010-08-24 15:38:56

Si je ne me trompe pas, le décalage cyclique à gauche de 0xFF produit 0xFF et ce n'est pas ce que Daniel veut –

@Maciej: right ne fonctionnerait que pour la représentation 'sign and magnitude'. Je vais modifier ma réponse. –

Si vous travaillez sur des octets, la table de recherche doit être la plus rapide.

Pour les entiers plus grands, l'implémentation basée sur CMOV serait décente. Vous pouvez également utiliser les instructions SSE ici.

Source

2010-08-24 14:43:42 BarsMonster

Un exemple avec des instructions SSE? –

Si votre implémentation prend en charge décalage vers la droite arithmétique des valeurs signées, essayez ceci:

#define MAP(x) ((x)<<1^(x)>>sizeof(x)*CHAR_BIT-1)

Pour les implémentations qui n'ont pas signé-décalage vers la droite, vous peut utiliser:

#define RSHIFT(x,n) ((x)>>n | \ 
    (-(1 & (x)>>sizeof(x)*CHAR_BIT-1))<<sizeof(x)*CHAR_BIT-1-n<<1))

(Vous devriez vérifier pour l'exactitude ...)

Source

2010-08-24 23:46:39

Quel est le moyen le plus rapide pour implémenter la carte signée à non signée r (x) = 2x-1 si x> 0 et r (x) = 2x autrement

Répondre

Questions connexes