applications pratiques des opérations par bitcoins

Question

1. À quoi ont servi les opérations de type "bitwise" ?
2. pourquoi sont-ils si pratiques ?
3. Quelqu'un peut-il recommander un tutoriel TRES simple ?

Answer 1

Bien que tout le monde semble être accroché au cas d'utilisation des drapeaux, ce n'est pas la seule application des opérateurs bitwise (même si c'est probablement la plus courante). De plus, C# est un langage d'un niveau suffisamment élevé pour que d'autres techniques soient rarement utilisées, mais cela vaut quand même la peine de les connaître. Voici ce à quoi je peux penser :

---

En << y >> peuvent rapidement multiplier par une puissance de 2. Bien sûr, l'optimiseur JIT de .NET le fera probablement pour vous (et tout compilateur décent d'un autre langage également), mais si vous vous souciez vraiment de chaque microseconde, vous pouvez écrire ceci pour être sûr.

Une autre utilisation courante de ces opérateurs consiste à fusionner deux entiers de 16 bits en un entier de 32 bits. Par exemple :

int Result = (shortIntA << 16 ) | shortIntB;

Cela est courant pour l'interfaçage direct avec les fonctions Win32, qui utilisent parfois cette astuce pour des raisons héritées du passé.

Et, bien sûr, ces opérateurs sont utiles lorsque vous voulez confondre les personnes inexpérimentées, comme lorsque vous fournissez une réponse à une question de devoir :)

Cependant, dans un code réel, il est préférable d'utiliser la multiplication, car elle est beaucoup plus lisible et le JIT l'optimise à shl y shr Il n'y a donc pas de pénalité de performance.

---

De nombreuses astuces curieuses concernent la ^ (XOR). Il s'agit en fait d'un opérateur très puissant, en raison des propriétés suivantes :

• A^B == B^A
• A^B^A == B
• Si vous connaissez A^B il est alors impossible de savoir ce qu'est un A y B sont, mais si vous connaissez l'un d'entre eux, vous pouvez calculer l'autre.
• L'opérateur ne souffre d'aucun débordement comme la multiplication/division/addition/soustraction.

J'ai vu quelques astuces utilisant cet opérateur :

Échange de deux variables entières sans variable intermédiaire :

A = A^B // A is now XOR of A and B
B = A^B // B is now the original A
A = A^B // A is now the original B

Liste à double lien avec une seule variable supplémentaire par élément. Cette méthode ne sera guère utilisée en C#, mais elle pourrait s'avérer utile pour la programmation de bas niveau des systèmes embarqués, où chaque octet compte.

L'idée est de garder en mémoire le pointeur du premier élément, le pointeur du dernier élément et, pour chaque élément, de garder en mémoire les éléments suivants pointer_to_previous ^ pointer_to_next . De cette façon, vous pouvez parcourir la liste à partir de n'importe quelle extrémité, tout en réduisant de moitié la charge de travail par rapport à une liste chaînée traditionnelle. Voici le code C++ permettant de parcourir la liste :

ItemStruct *CurrentItem = FirstItem, *PreviousItem=NULL;
while (  CurrentItem != NULL )
{
    // Work with CurrentItem->Data

    ItemStruct *NextItem = CurrentItem->XorPointers ^ PreviousItem;
    PreviousItem = CurrentItem;
    CurrentItem = NextItem;
}

Pour traverser à partir de la fin, il suffit de changer la toute première ligne de FirstItem à LastItem . Il s'agit là d'une autre économie de mémoire.

J'utilise également l'outil ^ Je rencontre régulièrement l'opérateur HashCode en C# lorsque je dois calculer un HashCode pour mon type qui est un type composite. Par exemple :

class Person
{
    string FirstName;
    string LastName;
    int Age;

    public int override GetHashCode()
    {
        return (FirstName == null ? 0 : FirstName.GetHashCode()) ^
            (LastName == null ? 0 : LastName.GetHashCode()) ^
            Age.GetHashCode();
    }
}

Answer 2

J'utilise les opérateurs bitwise pour la sécurité dans mes applications. Je stockerai les différents niveaux à l'intérieur d'une Enum :

[Flags]
public enum SecurityLevel
{
    User = 1, // 0001
    SuperUser = 2, // 0010
    QuestionAdmin = 4, // 0100
    AnswerAdmin = 8 // 1000
}

Puis assigner à un utilisateur ses niveaux :

// Set User Permissions to 1010
//
//   0010
// | 1000
//   ----
//   1010
User.Permissions = SecurityLevel.SuperUser | SecurityLevel.AnswerAdmin;

Ensuite, vérifiez les autorisations de l'action en cours :

// Check if the user has the required permission group
//
//   1010
// & 1000
//   ----
//   1000
if( (User.Permissions & SecurityLevel.AnswerAdmin) == SecurityLevel.AnswerAdmin )
{
    // Allowed
}

Answer 3

Je ne sais pas à quel point la résolution d'un sudoku vous semble pratique, mais supposons qu'elle le soit.

Imaginez que vous souhaitiez écrire un programme de résolution de sudoku, ou même simplement un programme simple, qui vous montre le tableau et vous permet de résoudre le puzzle vous-même, tout en s'assurant que les mouvements sont légaux.

Le tableau lui-même sera très probablement représenté par un tableau à deux dimensions du type :

uint [, ] theBoard = new uint[9, 9];

Valeur 0 signifie que la cellule est toujours vide et que les valeurs de l'intervalle [1u, 9u] sont les valeurs réelles du tableau.

Imaginez maintenant que vous souhaitiez vérifier si un mouvement est légal. Vous pouvez évidemment le faire avec quelques boucles, mais les bitmasks vous permettent d'aller beaucoup plus vite. Dans un programme simple qui se contente de vérifier que les règles sont respectées, cela n'a pas d'importance, mais dans un solveur, cela pourrait en avoir.

Vous pouvez gérer des tableaux de bitmasks, qui stockent des informations sur les nombres déjà insérés dans chaque ligne, chaque colonne a et chaque boîte 3x3.

uint [] maskForNumbersSetInRow = new uint[9];

uint [] maskForNumbersSetInCol = new uint[9];

uint [, ] maskForNumbersSetInBox = new uint[3, 3];

La correspondance entre le nombre et le schéma binaire, avec un bit correspondant à ce jeu de chiffres, est très simple.

1 -> 00000000 00000000 00000000 00000001
2 -> 00000000 00000000 00000000 00000010
3 -> 00000000 00000000 00000000 00000100
...
9 -> 00000000 00000000 00000001 00000000

En C#, vous pouvez calculer le schéma binaire de cette manière ( value es un uint ) :

uint bitpattern = 1u << (int)(value - 1u);

Dans la ligne ci-dessus 1u correspondant au schéma binaire 00000000 00000000 00000000 00000001 est décalé vers la gauche de value - 1 . Si, par exemple value == 5 vous obtenez

00000000 00000000 00000000 00010000

Au début, le masque de chaque ligne, colonne et case est le suivant 0 . Chaque fois que vous inscrivez un nombre sur la carte, vous mettez à jour le masque, de sorte que le bit correspondant à la nouvelle valeur est activé.

Supposons que vous insériez la valeur 5 à la ligne 3 (les lignes et les colonnes sont numérotées à partir de 0). Le masque de la ligne 3 est stocké dans maskForNumbersSetInRow[3] . Supposons également qu'avant l'insertion, il y avait déjà des nombres {1, 2, 4, 7, 9} à la ligne 3. Le schéma de bits dans le masque maskForNumbersSetInRow[3] ressemble à ceci :

00000000 00000000 00000001 01001011
bits above correspond to:9  7  4 21

L'objectif est d'activer le bit correspondant à la valeur 5 dans ce masque. Vous pouvez le faire en utilisant l'opérateur bitwise ou ( | ). Vous créez d'abord un motif binaire correspondant à la valeur 5

uint bitpattern = 1u << 4; // 1u << (int)(value - 1u)

puis vous utilisez le operator | pour activer le bit dans le masque maskForNumbersSetInRow[3]

maskForNumbersSetInRow[3] = maskForNumbersSetInRow[3] | bitpattern;

ou en utilisant la forme abrégée

maskForNumbersSetInRow[3] |= bitpattern;

00000000 00000000 00000001 01001011
                 |
00000000 00000000 00000000 00010000
                 =
00000000 00000000 00000001 01011011

Or votre masque indique qu'il existe des valeurs {1, 2, 4, 5, 7, 9} dans cette rangée (rangée 3).

Si vous souhaitez vérifier si une valeur se trouve dans la ligne, vous pouvez utiliser la fonction operator & pour vérifier si le bit correspondant est activé dans le masque. Si le résultat de cet opérateur appliqué au masque et à un motif de bit, correspondant à cette valeur, est différent de zéro, la valeur se trouve déjà dans la ligne. Si le résultat est 0, la valeur n'est pas dans la ligne.

Par exemple, si vous voulez vérifier si la valeur 3 se trouve dans la ligne, vous pouvez le faire de cette façon :

uint bitpattern = 1u << 2; // 1u << (int)(value - 1u)
bool value3IsInRow = ((maskForNumbersSetInRow[3] & bitpattern) != 0);

00000000 00000000 00000001 01001011 // the mask
                 |
00000000 00000000 00000000 00000100 // bitpattern for the value 3
                 =
00000000 00000000 00000000 00000000 // the result is 0. value 3 is not in the row.

Vous trouverez ci-dessous des méthodes pour définir une nouvelle valeur dans le tableau, pour maintenir à jour les masques de bits appropriés et pour vérifier si un mouvement est légal.

public void insertNewValue(int row, int col, uint value)
{

    if(!isMoveLegal(row, col, value))
        throw ...

    theBoard[row, col] = value;

    uint bitpattern = 1u << (int)(value - 1u);

    maskForNumbersSetInRow[row] |= bitpattern;

    maskForNumbersSetInCol[col] |= bitpattern;

    int boxRowNumber = row / 3;
    int boxColNumber = col / 3;

    maskForNumbersSetInBox[boxRowNumber, boxColNumber] |= bitpattern;

}

Avec les masques, vous pouvez vérifier si le mouvement est légal de la manière suivante :

public bool isMoveLegal(int row, int col, uint value)
{

    uint bitpattern = 1u << (int)(value - 1u);

    int boxRowNumber = row / 3;
    int boxColNumber = col / 3;

    uint combinedMask = maskForNumbersSetInRow[row] | maskForNumbersSetInCol[col]
                        | maskForNumbersSetInBox[boxRowNumber, boxColNumber];

    return ((theBoard[row, col] == 0) && ((combinedMask & bitpattern) == 0u);
}

Answer 4

Ils peuvent être utilisés pour toute une série d'applications différentes. Voici une question que j'ai déjà postée ici, qui utilise les opérations bitwise :

Question sur l'AND binaire, l'OR inclusif binaire, en Java

Pour d'autres exemples, voir les énumérations marquées (par exemple).

Dans mon exemple, j'ai utilisé des opérations par bit pour modifier la plage d'un nombre binaire de -128...127 à 0...255 (en changeant sa représentation de signée à non signée).

l'article de MSN ici ->

http://msdn.microsoft.com/en-us/library/6a71f45d%28VS.71%29.aspx

est utile.

Et, bien que ce lien :

http://weblogs.asp.net/alessandro/archive/2007/10/02/bitwise-operators-in-c-or-xor-and-amp-amp-not.aspx

est très technique, il couvre tout.

HTH

Answer 5

Chaque fois que vous avez le choix entre une ou plusieurs options en com

S