Quelle est votre technique préférée au niveau du bit? [fermé]

Il y a quelques jours, Anto, membre de StackExchange, s'est renseigné sur les utilisations valides des opérateurs bit à bit. J'ai déclaré que le décalage était plus rapide que la multiplication et la division d'entiers par des puissances de deux. Daemin, membre de StackExchange, a répliqué en déclarant que le décalage vers la droite présentait des problèmes avec les nombres négatifs.

À ce stade, je n'avais jamais vraiment pensé à utiliser les opérateurs de décalage avec des entiers signés. J'ai principalement utilisé cette technique dans le développement de logiciels de bas niveau; par conséquent, j'ai toujours utilisé des entiers non signés. C effectue des décalages logiques sur des entiers non signés. Aucune attention n'est accordée au bit de signe lors de l'exécution d'un décalage logique vers la droite. Les bits libérés sont remplis de zéros. Cependant, C effectue une opération de décalage arithmétique lors du décalage vers la droite d'un entier signé. Les bits libérés sont remplis du bit de signe. Cette différence fait arrondir une valeur négative vers l'infini au lieu d'être tronquée vers zéro, ce qui est un comportement différent de la division entière signée.

Quelques minutes de réflexion ont abouti à une solution de premier ordre. La solution convertit conditionnellement les valeurs négatives en valeurs positives avant le décalage. Une valeur est conditionnellement reconvertie dans sa forme négative après que l'opération de décalage a été effectuée.

int a = -5;
int n = 1;

int negative = q < 0; 

a = negative ? -a : a; 
a >>= n; 
a = negative ? -a : a; 

Le problème avec cette solution est que les instructions d'affectation conditionnelles sont généralement traduites en au moins une instruction de saut, et les instructions de saut peuvent être coûteuses sur les processeurs qui ne décodent pas les deux chemins d'instruction. Le fait de devoir réamorcer deux fois un pipeline d'instructions constitue une bonne réduction de tout gain de performance obtenu en déplaçant la division.

Cela dit, je me suis réveillé samedi avec la réponse au problème d'affectation conditionnelle. Le problème d'arrondi que nous rencontrons lors de l'exécution d'une opération de décalage arithmétique se produit uniquement lorsque nous travaillons avec la représentation du complément à deux. Cela ne se produit pas avec la représentation du complément. La solution au problème consiste à convertir une valeur de complément à deux en valeur de complément à un avant d'effectuer l'opération de décalage. Nous devons ensuite reconvertir la valeur du complément à un en valeur du complément à deux. Étonnamment, nous pouvons effectuer cet ensemble d'opérations sans convertir conditionnellement les valeurs négatives avant d'effectuer l'opération de décalage.

int a = -5;
int n = 1;

register int sign = (a >> INT_SIZE_MINUS_1) & 1

a = (a - sign) >> n + sign;   

La valeur négative du complément à deux est convertie en valeur négative du complément à un en soustrayant un. D'un autre côté, la valeur négative du complément à un est convertie en valeur négative du complément à deux en ajoutant un. Le code répertorié ci-dessus fonctionne car le bit de signe est utilisé pour convertir le complément à deux en complément à un et vice versa . Seules les valeurs négatives auront leurs bits de signe définis; par conséquent, le signe variable sera égal à zéro lorsque a est positif.

Cela dit, pouvez-vous penser à d'autres hacks au niveau du bit comme celui ci-dessus qui ont fait partie de votre sac d'astuces? Quel est votre hack au niveau du bit préféré? Je suis toujours à la recherche de nouveaux hacks bit à bit axés sur les performances.

J'adore le hack de Gosper (HAKMEM # 175), une façon très astucieuse de prendre un nombre et d'obtenir le numéro suivant avec le même nombre de bits défini. Il est utile, par exemple, pour générer des combinaisons d' kéléments à partir de ce qui nsuit:

int set = (1 << k) - 1;
int limit = (1 << n);
while (set < limit) {
    doStuff(set);

    // Gosper's hack:
    int c = set & -set;
    int r = set + c;
    set = (((r^set) >>> 2) / c) | r;
}

La méthode de la racine carrée inverse rapide utilise les techniques de niveau binaire les plus bizarres pour calculer l'inverse d'une racine carrée que j'ai jamais vue:

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking [sic]
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? [sic]
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
    //    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

Division par 3 - sans recourir à un appel de bibliothèque d'exécution.

Il s'avère que la division par 3 (grâce à un indice sur Stack Overflow) peut être approximée comme suit:

X / 3 = [(x / 4) + (x / 12)]

Et X / 12 est (x / 4) / 3. Il y a un élément de récursion qui apparaît soudainement ici.

Il s'avère également que si vous limitez la plage des numéros dans lesquels vous jouez, vous pouvez limiter le nombre d'itérations nécessaires.

Et donc, pour les entiers non signés <2000, ce qui suit est un algorithme rapide et simple / 3. (Pour de plus grands nombres, ajoutez simplement plus d'étapes). Les compilateurs optimisent le diable pour que cela finisse par être rapide et petit:

static unsigned short FastDivide3 (const unsigned short arg)
{
  RunningSum court non signé;
  FractionalTwelth court non signé;

  RunningSum = arg >> 2;

  FractionalTwelth = RunningSum >> 2;
  RunningSum + = FractionalTwelth;

  FractionalTwelth >> = 2;
  RunningSum + = FractionalTwelth;

  FractionalTwelth >> = 2;
  RunningSum + = FractionalTwelth;

  FractionalTwelth >> = 2;
  RunningSum + = FractionalTwelth;

  // Plus de répétitions des 2 lignes ci-dessus pour plus de précision

  return RunningSum;
}

Si vous regardez dans Erlang, il existe un DSL complet pour effectuer des opérations sur les bits. Donc, vous pouvez simplement décomposer une structure de données par bits en disant quelque chose comme ceci:

<> = << 1,17,42: 16 >>.

Tous les détails ici: http://www.erlang.org/doc/reference_manual/expressions.html#id75782