75 votes

les applications pratiques des opérations au niveau du bit

  1. Qu'avez-vous utilisé des opérations bit à bit pour?
  2. pourquoi sont-ils tellement à portée de main?
  3. quelqu'un peut s'il vous plaît recommander un TRÈS simple tutoriel?

80voto

Vilx- Points 37939

Bien que tout le monde semble être accroché sur les drapeaux de cas d'utilisation, qui n'est pas la seule application des opérateurs au niveau du bit (bien que probablement le plus commun). Aussi le C# est un assez haut niveau de la langue que d'autres techniques seront probablement rarement utilisé, mais il est toujours intéressant de les connaître. Voici ce que je pense:


L' << et >> opérateurs peuvent rapidement se multiplier par une puissance de 2. Bien sûr, l' .NET JIT optimiseur va probablement le faire pour vous (et tout bon compilateur d'une autre langue), mais si vous êtes vraiment à se préoccuper de chaque microseconde, vous pourriez écrire ceci pour être sûr.

Une autre utilisation courante de ces opérateurs est de farcir deux entiers de 16 bits en un entier de 32 bits. Comme:

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

Ce qui est commun pour l'interfaçage direct avec les fonctions Win32, qui parfois utiliser cette astuce pour des raisons d'héritage.

Et, bien sûr, ces opérateurs sont utiles lorsque vous souhaitez confondre l'expérience, comme lors de la fourniture d'une réponse à des devoirs à faire à la question. :)

Dans tout le code réel, si vous serez beaucoup mieux en utilisant la multiplication au lieu de cela, parce qu'il a une bien meilleure lisibilité et le JIT il optimise pour shl et shr instructions de toute façon, alors il n'y a pas de perte de performance.


Quelques curieux astuces traiter avec l' ^ opérateur (XOR). C'est en fait un très puissant opérateur, en raison des propriétés suivantes:

  • A^B == B^A
  • A^B^A == B
  • Si vous connaissez A^B alors qu'il est impossible de dire ce que A et B , mais si tu connais un d'entre eux, vous pouvez calculer l'autre.
  • L'opérateur ne souffre pas de tous les débordements, comme la multiplication/division/addition/soustraction.

Un couple de trucs que j'ai vu à l'aide de cet opérateur:

La permutation de deux variables de type entier, sans l'intermédiaire de la variable:

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 liaison avec juste une variable supplémentaire par article. Cela aura peu utiliser en C#, mais il pourrait venir dans maniable à faible niveau de programmation de systèmes embarqués où tous les compteurs d'octets.

L'idée est que vous garder une trace d'un pointeur pour le premier élément; le pointeur pour le dernier élément; et pour chaque élément de garder la trace de l' pointer_to_previous ^ pointer_to_next. De cette façon, vous pouvez parcourir la liste à partir de chaque extrémité, mais la surcharge est juste la moitié de celle d'une traditionnelle liste liée. Voici le code C++ pour la traversée:

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

    ItemStruct *NextItem = CurrentItem ^ PreviousItem;
    PreviousItem = CurrentItem;
    CurrentItem = NextItem;
}

À parcourir à partir de la fin vous avez juste besoin de changer la première ligne de FirstItem de LastItem. C'est une autre mémoire d'économie là.

Un autre endroit où je utiliser l' ^ de l'opérateur sur une base régulière en C#, c'est quand je dois calculer un HashCode pour mon type qui est un type composite. Comme:

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();
    }
}

69voto

Justin Niessner Points 144953

J'utilise les opérateurs sur les bits pour la sécurité dans mes applications. Je vais stocker les différents niveaux à l'intérieur d'un Enum:

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

Et puis affectez un utilisateur à leurs niveaux:

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

Et ensuite, vérifiez les autorisations dans l'action en cours:

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

16voto

Maciej Hehl Points 4760

Je ne sais pas comment pratique, la résolution d'un sudoku que vous considérez être, mais supposons qu'il est.

Imaginez que vous voulez écrire un solveur de sudoku ou même juste un programme simple, qui vous montre la carte et permet de résoudre le puzzle vous-même, mais assure que les mouvements sont légales.

Le conseil d'administration lui-même sera plus que probablement être représentée par un tableau à deux dimensions comme:

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

Valeur en 0 signifie que la cellule reste vide et les valeurs de l'intervalle [1u, 9u] sont les valeurs réelles dans le conseil d'administration.

Maintenant, imaginez que vous voulez vérifier si un mouvement est légal. Évidemment, vous pouvez le faire avec un peu de boucles, mais les masques binaires vous permettent de faire des choses beaucoup plus rapidement. Dans un programme simple qui s'assure juste que les règles sont respectées, il n'a pas d'importance, mais dans un solveur il le pouvait.

Vous pouvez maintenir des tableaux de masques de bits, qui stockent des informations sur les numéros qui sont déjà insérés dans chaque ligne, chaque colonne 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 numéro de la bitpattern, avec un bit correspondant à ce numéro, 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 l'bitpattern de cette façon (value est uint):

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

Dans la ligne ci-dessus 1u correspondant à la bitpattern 00000000 00000000 00000000 00000001 est décalé à gauche par value - 1. Si, par exemple, value == 5, vous obtenez

00000000 00000000 00000000 00010000

Au début, le masque, pour chaque ligne, colonne et boîte est - 0. Chaque fois que vous mettez un certain nombre sur la carte, vous mettez à jour le masque, de sorte que le bit correspondant à la nouvelle valeur est définie.

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

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

L'objectif est de définir le bit correspondant à la valeur 5 dans ce masque. Vous pouvez le faire en utilisant l'opérateur or (|). Tout d'abord vous créer un motif de bits correspondant à la valeur 5

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

et puis vous utilisez l' operator | pour définir les bits dans le masque maskForNumbersSetInRow[3]

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

ou à l'aide de formulaire plus court

maskForNumbersSetInRow[3] |= bitpattern;

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

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

Si vous voulez vérifier, si la valeur est dans la ligne, vous pouvez utiliser operator & pour vérifier si le bit correspondant est défini dans le masque. Si le résultat de cet opérateur appliqué le masque et d'un motif de bits, correspondant à cette valeur est non nulle, la valeur est 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 est en 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.

Ci-dessous sont des méthodes pour la définition d'une nouvelle valeur dans le conseil, le maintien des masques de bits à jour et vérifier si un déplacement 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;

}

Avoir les masques, vous pouvez vérifier si le mouvement est légal comme ceci:

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);
}

2voto

Dave Points 3005

Ils peuvent être utilisés pour un chargement entier de différentes applications, voici une question que j'ai déjà posté ici, qui utilise des opérations bit à bit:

http://stackoverflow.com/questions/560956/bitwise-and-bitwise-inclusive-or-question-in-java

Pour d'autres exemples, ont un oeil à (dire) a suscité des énumérations.

Dans mon exemple, j'ai été en utilisant les opérations bit à bit à modifier la portée d'un nombre binaire de -128...127 0..255 (changement de la représentation de signé non signé).

le MSN article ici ->

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

est utile.

Et, même si 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 est tout couvrant.

HTH

2voto

Chris Lively Points 59564

À tout moment vous avez la possibilité de 1 ou plus dans la combinaison des éléments, puis au niveau du bit est généralement une solution facile.

Quelques exemples incluent la sécurité bits (en attente sur Justin exemple..), planification des journées, etc.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X