A quoi sert ce morceau de programme..?

[Kinouss]

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]

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]

on dirait une sorte de fonction de hash farfelue...

[Kinouss]

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]

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

[theocrite]

C'est pas mal tordu quand même.

[tibtib17]

Complètement tordu quand même...

[pseudocode]

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]

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]

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]

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]

Le premier qui pond un code comme ça, je le jette de l'équipe...

Aucune doc, algorithme farfelu... totalement inmaintenable.

[Charles.w]

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