Quelle doit être la qualité d'un programmeur complet pour effectuer des opérations binaires? [fermé]

J'ai récemment parcouru du code OpenJDK et y ai trouvé des éléments de code intrigants liés à des opérations au niveau des bits . J'ai même posé une question à ce sujet sur StackOverflow.

Un autre exemple qui illustre le point:

 1141       public static int bitCount(int i) {
 1142           // HD, Figure 5-2
 1143           i = i - ((i >>> 1) & 0x55555555);
 1144           i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
 1145           i = (i + (i >>> 4)) & 0x0f0f0f0f;
 1146           i = i + (i >>> 8);
 1147           i = i + (i >>> 16);
 1148           return i & 0x3f;
 1149       }

Ce code peut être trouvé dans la classe Integer .

Je ne peux pas m'empêcher de me sentir stupide quand je regarde ça. Ai-je manqué une classe ou deux au collège ou est-ce que ce n'est pas quelque chose que je suis supposé avoir ? Je peux faire quelques opérations simples (comme ANDing, ORing, XORing, shifting), mais bon, comment quelqu'un peut-il arriver avec un code comme celui-ci?

Quelle doit être la qualité d'un programmeur complet pour effectuer des opérations binaires?

Sur une note de côté ... Ce qui m'inquiète, c'est que la personne qui a répondu à ma question sur StackOverflow y a répondu en quelques minutes. S'il pouvait faire cela, pourquoi ai-je simplement regardé comme un cerf dans les phares?

Je dirais qu'en tant que développeur bien équilibré, vous devez comprendre les opérateurs et les opérations au niveau des bits.

Donc, au minimum, vous devriez être capable de comprendre le code ci-dessus après un peu de réflexion.

Les opérations au niveau des bits ont tendance à être plutôt faibles. Par conséquent, si vous travaillez sur des sites Web et des logiciels LOB, il est peu probable que vous les utilisiez beaucoup.

Comme d’autres choses, si vous ne les utilisez pas beaucoup, vous n’y connaîtrez rien.

Donc, ne vous inquiétez pas du fait que quelqu'un puisse résoudre le problème très rapidement, car il (probablement) travaille beaucoup avec ce type de code. Peut-être écrire du code OS, du code du pilote ou une autre manipulation délicate.

Si vous comprenez comment résoudre des problèmes tels que "déterminer si les bits 3 et 8 sont définis", "effacer le bit 5" ou "trouver la valeur entière représentée par les bits 7-12", vous avez suffisamment de connaissances des opérateurs au niveau du bit pour vérifier le Can. La boîte Twiddle Bits de la liste de contrôle " complète ".

Le contenu de votre exemple provient de Hacker's Delight , une compilation d'algorithmes hautes performances permettant de manipuler de petits bits de données, tels que des entiers. Quiconque a écrit ce code à l'origine ne l'a pas craché en moins de cinq minutes; L’histoire qui s’y rattache est plus susceptible de nécessiter un moyen rapide et sans branche de compter les bits, et l’auteur a eu le temps de passer du temps à regarder des chaînes de bits et à trouver un moyen de résoudre le problème. Personne ne comprendra comment cela fonctionne d'un coup d'œil, à moins de l'avoir déjà vu auparavant. Avec une solide compréhension des bases du bit et un peu de temps passé à expérimenter le code, vous pourriez probablement comprendre comment il fait ce qu'il fait.

Même si vous ne comprenez pas ces algorithmes, le simple fait de les connaitre ajoute à votre "arrondi", car lorsque vient le temps de traiter, par exemple, du comptage de bits haute performance, vous savez quoi étudier. Avant Google, il était beaucoup plus difficile de trouver ces informations. maintenant c'est loin des frappes.

L'utilisateur qui a répondu à votre question SO a peut-être déjà vu le problème ou a étudié le hachage. Ecris-le et demande.

Dans votre exemple, vous devez absolument savoir certaines choses sans vraiment y penser.

1143 i = i - ((i >>> 1) & 0x55555555);

Vous devez reconnaître le motif de bits 0x555 ... comme étant un motif de bits alternatif 0101 0101 0101 et que les opérateurs le décalent d'un bit (à droite), et que & est une opération de masquage (et ce que signifie masquage).

1144 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

Encore un motif, celui-ci est 0011 0011 0011. En outre, il en déplace deux cette fois et le masque à nouveau. le déplacement et le masquage suivent un modèle que vous devriez reconnaître ...

1145 i = (i + (i >>> 4)) & 0x0f0f0f0f;

le motif se solidifie. Cette fois, il s'agit de 00001111, 00001111 et, bien sûr, nous le déplaçons cette fois-ci. nous nous déplaçons chaque fois par la taille du masque.

1148 renvoyer i & 0x3f;

un autre motif binaire, 3f est un bloc de zéros suivi d’un bloc plus grand.

Toutes ces choses devraient être évidentes en un coup d'œil si vous êtes "bien rond". Même si vous ne pensez jamais l'utiliser, vous manquerez probablement certaines possibilités de simplifier considérablement votre code si vous ne le savez pas.

Même dans un langage de niveau supérieur, les modèles de bits sont utilisés pour stocker BEAUCOUP de plus grandes quantités de données dans des champs plus petits. C’est la raison pour laquelle vous voyez toujours des limites de 127/8, 63/4 et 255/6 dans les jeux. C’est parce que vous devez stocker tellement de choses que, sans emballer les champs, vous serez obligé d’utiliser dix fois plus de quantité de mémoire. (Et bien, le meilleur serait que si vous deviez stocker un grand nombre de booléens dans un tableau, vous pourriez économiser 32 à 64 fois la quantité de mémoire que vous utiliseriez si vous n'y pensiez pas - la plupart des langues implémentent des booléens Un mot qui sera souvent au format 32 bits: ceux qui ne se sentent pas à l'aise à ce niveau résisteront aux occasions de stocker de telles données simplement parce qu'ils ont peur de l'inconnu.

Ils craindront également des choses telles que l'analyse manuelle des paquets livrés sur le réseau dans un format compacté - chose triviale si vous n'avez pas peur. Cela pourrait prendre un jeu nécessitant un paquet de 1k à 200 octets, le plus petit paquet glissant plus efficacement sur le réseau, réduisant la latence et permettant des vitesses d’interaction plus élevées (pouvant permettre de nouveaux modes de jeu complets pour un jeu).

Il m'est arrivé de reconnaître le code parce que je l'avais déjà vu dans un logiciel de manipulation d'images vidéo. Si vous travailliez régulièrement avec des CODEC audio et vidéo, des protocoles réseau ou des registres à puce, vous verriez beaucoup d'opérations bit à bit et cela deviendrait une seconde nature pour vous.

Vous ne devriez pas vous sentir mal si votre travail ne coïncide pas très souvent avec ces domaines. Je connais bien les opérations au niveau des bits, mais je ralentis les rares occasions où j’ai besoin d’écrire une interface graphique, à cause de toutes les bizarreries liées à la disposition, à la pondération et à l’agrandissement, de sorte que, j'en suis sûr, une seconde nature pour les autres. Vos points forts sont ceux où vous avez le plus d’expérience.

les principales choses à savoir sont la manière dont les entiers sont représentés (en général, un vecteur de bits de longueur fixe où la longueur dépend de la plate-forme) et les opérations disponibles sur ceux-ci.

les principales opérations arithmétiques + - * / %peuvent être comprises sans avoir besoin de le comprendre, bien que cela puisse être pratique pour les micro-optimisations (bien que la plupart du temps, le compilateur sera en mesure de s'en charger pour vous)

l'ensemble de manipulation de bits | & ~ ^ << >> >>>nécessite au moins une compréhension de passage pour pouvoir les utiliser

Cependant, la plupart du temps, vous ne les utiliserez que pour transmettre des indicateurs de bits à une méthode . Ainsi, il est plus lisible de transmettre ORun int, puis d' ANDextraire les paramètres, que de passer plusieurs booléens (jusqu'à 32) dans une longue liste de paramètres. les drapeaux possibles pour changer sans changer d'interface

pour ne pas mentionner les booléens sont généralement conservés séparément en octets ou en ints au lieu de les assembler comme le font les drapeaux

quant à l'extrait de code, il effectue un comptage parallèle des bits, ce qui permet à l'algorithme de s'exécuter dans O(log(n))lequel n est le nombre de bits au lieu de la boucle naïve qui estO(n)

la première étape est la plus difficile à comprendre, mais si vous partez de la configuration, il faut remplacer les séquences de bits 0b00à 0b00, 0b01à 0b01, 0b10à 0b01et 0b11à 0b10il devient plus facile à suivre

donc pour la première étape i - ((i >>> 1) & 0x55555555)si nous prenons ipour être égal à 0b00_01_10_11alors la sortie de cela devrait être0b00_01_01_10

(note qui 0x5est égal à 0b0101)

iuf nous prenons i = 0b00_01_10_11cela signifie que 0b00_01_01_10 - (0b00_00_11_01 & 0b01_01_01_01)c’est 0b00_01_10_11 - 0b00_00_01_01ce qui devient0b00_01_01_10

ils auraient pu le faire (i & 0x55555555) + ((i >>> 1) & 0x55555555)pour le même résultat, mais il s'agit d'une opération supplémentaire

les étapes suivantes vont dans le même sens

Tout le monde devrait comprendre les opérations de base en bits. C’est la composition des opérations de base pour effectuer des tâches de manière optimisée et robuste qui demande beaucoup de pratique.

Ceux qui travaillent tous les jours avec des manipulations de bits (comme ceux qui sont intégrés) vont bien sûr développer une forte intuition et un sac à malice.

Quelle compétence un programmeur qui ne fait pas de choses de bas niveau devrait-il avoir avec une manipulation par bits? Assez pour pouvoir t'asseoir avec une strophe telle que celle que tu as collée et la parcourir lentement comme s'il s'agissait d'un casse-tête ou d'un casse-tête.

Dans le même ordre d'idées, je dirais qu'un programmeur intégré devrait comprendre autant de choses sur http qu'un développeur Web doit comprendre une manipulation au niveau des bits. En d'autres termes, il est "OK" de ne pas être manipulé si vous ne l'utilisez pas tout le temps.

Le plaisir du pirate informatique est un travail dérivé. L'ancêtre de tous est HakMem de 1972. http://w3.pppl.gov/~Hammett/work/2009/AIM-239-ocr.pdf

L'important est de savoir que l'algorithme évident pour n'importe quelle tâche n'est pas nécessairement le meilleur. Il existe de nombreux cas où il est important de connaître l' existence d'une solution élégante à un problème particulier.

Quelle est la difficulté d'interprétation des opérateurs de bits?

Je programme des systèmes embarqués. J'ai beaucoup pratiqué ce genre de choses. Votre question liée sur les cartes de hachage avec le code

static int hash(int h) {
   // This function ensures that hashCodes that differ only by
   // constant multiples at each bit position have a bounded
   // number of collisions (approximately 8 at default load factor).
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

Cela me paraissait parfaitement logique aussi longtemps qu'il faudrait pour dicter le code à voix haute. Les événements décrits dans bitCountsont immédiatement clairs, mais il faut une minute pour comprendre pourquoi il compte réellement les bits. Les commentaires seraient bien, cependant, et rendraient la compréhension de ce que le code ne fait que légèrement plus difficile que le problème du hash.

Il est important de faire la distinction entre lire et comprendre le code. Je peux interpréter le bitCountcode et lire ce qu'il fait, mais il faudrait une minute pour prouver pourquoi cela fonctionne ou même si cela fonctionne. Il y a une différence entre être capable de lire le code en douceur et être capable de comprendre pourquoi le code est ce qu'il est. Certains algorithmes sont simplement difficiles. Le quoi du hashcode avait un sens, mais le commentaire expliquait pourquoi ce qui était fait. Ne vous découragez pas si une fonction utilisant des opérateurs au niveau des bits est difficile à comprendre, ils sont souvent utilisés pour effectuer des calculs mathématiques complexes, ce qui serait difficile quel que soit le format.

Une analogie

Je suis habitué à ce genre de choses. Un sujet auquel je ne suis pas habitué est la regex. Je traite avec eux de temps en temps sur des scripts de construction, mais jamais dans le travail de développement quotidien.

Je sais comment utiliser les éléments suivants d'une regex:

• [] classes de personnage
• Les *, .et +wildcards
• Le début de la chaîne ^et la fin de la chaîne$
• Les classes de caractères \ d, \ w et \ s
• Le drapeau / g

C'est assez pour créer des requêtes simples, et beaucoup de requêtes que je vois ne s'en écartent pas.

Tout ce qui ne figure pas sur cette liste est une triche. Tout ce qui est, à l' exception {}et ()- La feuille de triche ne sera pas suffisant. J'en connais juste assez sur ces gars-là pour savoir que je vais avoir besoin d'un tableau blanc, d'un manuel de référence et peut-être d'un collègue. Vous pouvez intégrer des algorithmes délirants dans quelques lignes de regex.

Pour concevoir une expression rationnelle qui requiert ou suggère tout ce qui ne figure pas dans ma liste d'éléments connus, je vais énumérer toutes les classes d'entrées que je compte reconnaître et les placer dans une suite de tests. Je vais construire la regex lentement et progressivement, avec de nombreuses étapes intermittentes, et valider ces étapes pour le contrôle de la source et / ou les laisser dans un commentaire afin que je puisse comprendre ce qui était censé se passer plus tard quand elle se cassera. Si c'est dans le code de production, je vais m'assurer que celui-ci sera examiné par une personne plus expérimentée.

Est-ce là où vous en êtes avec les opérateurs au niveau des bits?

Donc, vous voulez être bien arrondi?

À mon avis, si vous êtes capable d'interpréter ce code comme celui-ci en tirant un morceau de papier ou en allant au tableau blanc et en parcourant les opérations manuellement, vous êtes qualifié comme complet. Pour être considéré comme un bon programmeur complet dans le domaine des opérations au niveau des bits, vous devez être capable de faire quatre choses:

1. Être capable de lire et d'écrire des opérations courantes de manière fluide
   Pour un programmeur d'applications, les opérations courantes avec des opérateurs au niveau des bits incluent les opérateurs de base de |et &pour définir et effacer des indicateurs. Cela devrait être facile. Vous devriez être capable de lire et d’écrire des choses comme

   open('file', O_WRONLY | O_APPEND | O_CREAT );
   // Use an OR operator ^ here and ^ here to set multiple flags
   

   sans ralentir (en supposant que vous sachiez ce que signifient les drapeaux ).

2. Pouvoir lire des opérations plus complexes avec un peu de travail
   Compter les bits très rapidement en temps O (log (n)) sans branches, en s'assurant que le nombre de collisions dans hashCodes peut différer d'un montant lié, et en analysant les adresses e-mail , numéros de téléphone ou HTML avec une regex sont des problèmes difficiles. Il est raisonnable que quiconque n'est pas un expert dans ces domaines cherche à obtenir le tableau blanc, il est déraisonnable de ne pas pouvoir commencer à travailler pour comprendre.

3. Etre capable d'écrire des algorithmes complexes avec beaucoup de travail
   Si vous n'êtes pas un expert, vous ne devriez pas vous attendre à être capable de faire des choses complexes et difficiles. Cependant, un bon programmeur devrait pouvoir le faire en travaillant continuellement. Faites cela assez souvent et vous serez bientôt un expert :)

Si vous êtes allé dans une université décente, vous auriez dû suivre un cours de mathématiques discrètes. Vous auriez appris les portes logiques et arithmétiques binaires, octales et hexadécimales.

Sur cette note, il est normal de se sentir dérouté par cela, si cela peut vous consoler, car j’écris principalement des applications Web, j’ai rarement besoin de regarder ou d’écrire du code comme celui-ci, mais puisque je comprends l’arithmétique binaire et le comportement des opérateurs au niveau du bit Je peux éventuellement comprendre ce qui se passe ici avec suffisamment de temps.

En tant que programmeur de téléphones mobiles, je devais faire face à ce genre de problème. Il est assez courant que le périphérique ne dispose pas de beaucoup de mémoire ou que la vitesse de transmission soit importante. Dans les deux cas, vous essayez de regrouper autant d'informations que possible dans quelques octets.

Je ne me souviens pas d’avoir utilisé des opérateurs au niveau des bits dans environ 5 ans de PHP (c’est peut-être juste moi), pas dans environ 10 ans de programmation Windows, bien que certains éléments de niveau inférieur de Windows contiennent des bits.

Vous dites "Je ne peux pas m'empêcher de me sentir stupide quand je regarde ça". NE PAS - se sentir en colère.

Vous venez de rencontrer la sortie d'un programmeur cow-boy.

Ne sait-il rien de l'écriture de code maintenable? J'espère sincèrement que c'est lui qui doit y revenir dans un an et essayer de se rappeler ce que cela signifie.

Je ne sais pas si vous coupez les commentaires ou s'il n'y en a pas, mais ce code ne permet pas de passer en revue le code dans lequel j'étais s / w QA manager (et je l'ai été quelques fois).

Voici une bonne règle empirique: les seuls "nombres entiers nus" autorisés dans le code sont 0 1 1. Tous les autres nombres doivent être #defines, coûts, enums, etc., en fonction de votre langue.

Si ces 3 et 0x33333333 ont dit quelque chose comme NUM_WIDGET_SHIFT_BITS et WIDGET_READ_MASK, le code aurait été plus facile à lire.

Honte à quiconque a mis cela dans un projet open source, mais même pour le code personnel, commentez bien et utilisez des définitions / énumérations significatives et appliquez vos propres normes de codage.

Ce morceau de code particulier est extrait du livre Hacker's Delight , figure 5.2. Son en ligne en C (la fonction pop) ici . Notez que l'auteur recommande maintenant d'utiliser des versions mises à jour: http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.c.txt

Si vous voulez apprendre ce genre de micro-optimisations, je vous suggérerais ce livre; c'est amusant, mais à moins que vous ne programmiez des bits de très bas niveau, vous ne le comprendrez probablement pas; et la plupart du temps, votre compilateur sera capable de faire bon nombre de ces optimisations pour vous.

Il est également utile de réécrire tous les nombres hexadécimaux en binaire pour comprendre ces types d'algorithmes et les utiliser dans un ou plusieurs cas de test.

Explication par exemple. Les données sont des séquences de bits. Comptons les bits sur l’octet 01001101 ayant les opérations suivantes disponibles: 1. Nous pouvons vérifier la valeur du dernier bit. 2. Nous pouvons décaler la séquence.

1. 01001101 -> le dernier octet est 1, total = 1. des changements
2. 10100110 -> le dernier octet est 0, total = 1. des changements
3. 01010011 -> le dernier octet est 1, total = 2. des changements
4. 10101001 -> le dernier octet est 1, total = 3. des changements
5. 11010100 -> le dernier octet est 0, total = 3. des changements
6. 01101010 -> le dernier octet est 0, total = 3. des changements
7. 00110101 -> le dernier octet est 1, total = 4. des changements
8. 10011010 -> le dernier octet est 0, total = 4. des changements

Notre réponse: 4.

Ce n'était pas difficile, n'est-ce pas? Le gros problème avec les opérations au niveau des bits est que nous pouvons faire des choses limitées. Nous ne pouvons pas accéder un peu directement. Mais nous pouvons, par exemple, connaître la valeur du dernier bit en le comparant au MASK 00000001 et faire en sorte que chaque bit soit le dernier avec les opérations de décalage. Bien entendu, l’algorithme résultant semblera effrayant pour ceux qui n’ont pas l'habitude de le faire. Rien à voir avec l'intelligence.

Je ne dirais pas que vous en avez besoin sauf si le travail que vous faites est lié à:

• Traitement audio
• Traitement vidéo
• Graphique
• Mise en réseau (particulièrement lorsque la taille des paquets est importante)
• D'énormes quantités de données

Stocker les autorisations dans des drapeaux de style unix est également une autre utilisation, si vous avez un modèle d’autorisations particulièrement complexe pour votre système, ou si vous voulez vraiment tout mettre dans un octet, au détriment de la lisibilité.

Mis à part ces domaines, je considérerais cela comme un gros avantage si un développeur / développeur senior pouvait démontrer un décalage, et utiliser | & et ^ car cela montre un intérêt pour la profession, ce qui pourrait conduire à un code plus stable et fiable.

Pour ce qui est de ne pas "obtenir" la méthode à première vue, comme mentionné, vous avez besoin d'une explication de ce qu'elle fait et de quelques informations de base. Je ne dirais pas que c'est lié au renseignement, mais que vous connaissez bien le fait de travailler au quotidien avec hexadécimal et de reconnaître les problèmes que certains modèles peuvent résoudre.