Kinouss Posté(e) le 15 décembre 2006 Posté(e) le 15 décembre 2006 Bonjour, pour les pros, ma question va sans doutes paraître stupide mais bon : A quoi sert le morceau de programme qui suit, écrit en C : int Devinez(int x) { int n=0; while(x!=0) { n = n+1; x = x & (x-1); } return n; } note : le '&' est l'opération et-booléenne. J'ai essayé de rentrer ce truc dans RQ Beta, et je n'obtiens rien... Que faire..? D'avance merci... Kinouss. - edit de Quarky : ajout des balises de code -
mogwai93 Posté(e) le 15 décembre 2006 Posté(e) le 15 décembre 2006 on dirait que ca retourne le nombre de 1 dans la representation binaire de X exemple : si X = 7 (111 en binaire) 1er passage : X = 7 N = 1 X = 7 & 6 (en binaire : 111 & 110) = 110 (donc 6) 2eme passage X = 6 N = 2 X = 6 & 5 (en binaire : 110 & 101) = 100 (donc 4) 3eme passage X = 4 N = 3 X = 4 & 3 (en binaire : 100 & 11) = 0 pas de 4eme passage on retourne 3 et 7 étant égal à 111 en binaire donc 3 1 à confirmer et l'utilité ? pour les resultats, ca semble être ça.... X N binaire 0 0 0 1 1 1 2 1 10 3 2 11 4 1 100 5 2 101 6 2 110 7 3 111 8 1 1000 9 2 1001 10 2 1010 100 3 1100100 1000 6 1111101000
lorinc Posté(e) le 15 décembre 2006 Posté(e) le 15 décembre 2006 on dirait une sorte de fonction de hash farfelue...
Kinouss Posté(e) le 15 décembre 2006 Auteur Posté(e) le 15 décembre 2006 on dirait que ca retourne le nombre de 1 dans la representation binaire de X exemple : si X = 7 (111 en binaire) 1er passage : X = 7 N = 1 X = 7 & 6 (en binaire : 111 & 110) = 110 (donc 6) 2eme passage X = 6 N = 2 X = 6 & 5 (en binaire : 110 & 101) = 100 (donc 4) 3eme passage X = 4 N = 3 X = 4 & 3 (en binaire : 100 & 11) = 0 pas de 4eme passage on retourne 3 et 7 étant égal à 111 en binaire donc 3 1 à confirmer et l'utilité ? pour les resultats, ca semble être ça.... X N binaire 0 0 0 1 1 1 2 1 10 3 2 11 4 1 100 5 2 101 6 2 110 7 3 111 8 1 1000 9 2 1001 10 2 1010 100 3 1100100 1000 6 1111101000 C'est absolument cela ! Après vérif auprès d'un pote qui est en IUT, sa réponse est la même... Merci à tous pour vos réponses... PS : Pour l'utilité... En fait c'est un type qui m'a posté cela en phase de recrutement pour tester mes connaissances... Ca à l'air mal barré pour moi !
mogwai93 Posté(e) le 15 décembre 2006 Posté(e) le 15 décembre 2006 deja pour savoir ce que ca fait : 1) faire quelques tests afin d'en deduire une regle 2) la presence d'un & ou d'un | veut dire qu'il y a un rapport avec le binaire donc voila
pseudocode Posté(e) le 16 décembre 2006 Posté(e) le 16 décembre 2006 C'est meme completement n'importequoi comme question. Je ne sais pas quel logiciel fabrique cette societe, mais si la technique de recutement consiste a trouver des developpeurs capable de faire du reverse-eng de code... arg ! Pour info, le code de Integer.bitCount() dans J2SE5 fait la meme chose en 6 lignes, sans faire de loop...
Dragohn Posté(e) le 16 décembre 2006 Posté(e) le 16 décembre 2006 Visiblement le recruteur n'a pas la moindre idée de ce qu'est un langage objet. Et en plus, il sait meme pas utiliser la javadoc de J2SE. Le code de Integer.bitCount() dans J2SE5 fait la meme chose en 6 lignes, sans faire de loop... Son programme est écrit en C, pas en Java On m'avait fait le même genre pour un recrutement, c'est assez récurrent (avec les pointeurs) quand je me tape des entretiens pour du C ou C++. Ca fait bizarre la 1ère fois, après on s'y attend un peu plus (en ce qui me concerne)
Jiriki Posté(e) le 16 décembre 2006 Posté(e) le 16 décembre 2006 Cette fonction retourne 1 si x est une puissance de 2, l'écart avec la puissance de 2 inférieure la plus proche sinon. Ex: X= 8 N=1 8&(8-1) == 8 & 7 == 1000 & 0111 == 0 => N=1 X=16 N=1 16&(16-1) == 16 & 15 == 10000 & 01111 == 0 => N=1 X= 7 N=1 7&(7-1) == 7&6 == 0111 & 0110 == 0110 == 6 ... => N=3 car 7-3 = 4 + voir les résultats de mogwai93
Wooden Posté(e) le 6 janvier 2007 Posté(e) le 6 janvier 2007 C'est meme completement n'importequoi comme question. Je ne sais pas quel logiciel fabrique cette societe, mais si la technique de recutement consiste a trouver des developpeurs capable de faire du reverse-eng de code... arg ! Pour info, le code de Integer.bitCount() dans J2SE5 fait la meme chose en 6 lignes, sans faire de loop... Peut être mais vas deviner tout seul ce que fait la fonction... public static int bitCount(int i) { // HD, Figure 5-2 i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; } ... on vas dire, que ça doit être bien optimisé
Sentinel Posté(e) le 6 janvier 2007 Posté(e) le 6 janvier 2007 Le premier qui pond un code comme ça, je le jette de l'équipe... Aucune doc, algorithme farfelu... totalement inmaintenable.
Charles.w Posté(e) le 16 janvier 2007 Posté(e) le 16 janvier 2007 Il ne vaut mieux pas que je t'envoie certaines corrections de TP de programmation que l'on a alors xD Sinon, c'est clair que c'est tordu...que c'est moche...et que ce n'est pas documenté, soit exactement ce qu'il ne faut pas faire...si tu as dis ca lors de l'entretien, ca peut les calmer un peu
Messages recommandés
Archivé
Ce sujet est désormais archivé et ne peut plus recevoir de nouvelles réponses.