/* Topic des codeurs couche-tard [2] */

Compteur du TdCCT · Le 27/11/2010, à 07:42

Scores de la période en cours :

1) 231    nesthib
2) 211    samuncle
3) 179    grim7reaper
4) 170    Кຼزດ
5) 142    cm-t
6) 140    nathéo
7) 127    Pylade
8) 124    gnuuat
9) 66    Askelon
10) 39    \\Ouranos//
10) 39    Lagierl
12) 37    tshirtman
13) 17    helly
14) 10    Р☢w ! ✰ :mad: ✰ (эй !)
15) 9    The Uploader
16) 8    Sherwood51
17) 5    Le Rouge
17) 5    Steap
19) 3    Kanor
20) 2    pierguiard
21) 1    xapantu

\\Ouranos// · Le 28/11/2010, à 00:20

grim7reaper · Le 28/11/2010, à 00:50

Allez, je vous propose un petit défi (rien de bien compliqué).

Écrivez le corps de la fonction (je vous fournis le prototype) qui positionne à 1 ou à 0 le bit n de la variable entière non-signé x.
Le but étant d'avoir la fonction la plus rapide et la plus petite possible (i.e qui a le moins d'instructions).

/**
 *     Fonction : unsigned int set_bit(unsigned int x, unsigned int n, unsigned int v)
 * Description : Positionne à v le bit n de la variable x
 *
 * x : variable à modifier.
 * n : position du bit à modifier (on commence a 0).
 * v : nouvelle valeur du bit (0 ou 1)
 * Sortie : Variable avec le bit n qui vaut v.
 */
unsigned int set_bit(unsigned int x, unsigned int n, unsigned int v)
{
    /* À vous de jouer ! */
}

Pas besoin de vérifier si v vaut 0 ou 1, ni de vérifier la validité de n.

Si personne ne trouve la bonne réponse d'ici demain soir, je donnerais la solution.

NB : je pars sur du C, mais si vous voulez proposer une solution dans un autre langage vous pouvez (par contre si c'est de l'interprété on ne pourra pas comparer le nombre d'instructions générées, mais de toute façon c'est surtout une question d'algo donc on ne devrait pas avoir à aller jusque là).

Dernière modification par grim7reaper (Le 28/11/2010, à 01:03)

compte supprimé · Le 28/11/2010, à 01:02

J'ai commencé un p'tit projet pygame : une compilation de jeux 8-bits. Pour l'instant j'ai juste les bases graphiques (écrans, widgets...) et de gestion des évènements.
Bonne nuit !

Pylades · Le 28/11/2010, à 01:15

#!/usr/bin/env python3.0

#     Fonction : unsigned int set_bit(unsigned int x, unsigned int n, unsigned int v)
# Description : Positionne à v le bit n de la variable x
#
# x : variable à modifier.
# n : position du bit à modifier (on commence a 0).
# v : nouvelle valeur du bit (0 ou 1)
# Sortie : Variable avec le bit n qui vaut v.

def set_bit(x, n, v):
    return (x & ~(2**n)) | ((2**n)*v)

Bon, j'ai mis plein de parenthèses pour faciliter la lecture, même si tu ne les aimes pas trop.
Mais curieusement, je sens qu'il y a moyen de faire beaucoup plus futé…

grim7reaper · Le 28/11/2010, à 01:19

Presque (je pensais pas avoir une réponse si proche du premier coup, ça va être rapide du coup ), mais là tu pourris toutes les perfs avec un horrible **
Arf, puis * aussi c'est moche.
J'ai demandé un truc rapide quand même, tu veux pas mettre un modulo tant que tu y es

Dernière modification par grim7reaper (Le 28/11/2010, à 01:20)

Кຼزດ · Le 28/11/2010, à 01:21

Pylade a écrit :

#!/usr/bin/env python3.0

#     Fonction : unsigned int set_bit(unsigned int x, unsigned int n, unsigned int v)
# Description : Positionne à v le bit n de la variable x
#
# x : variable à modifier.
# n : position du bit à modifier (on commence a 0).
# v : nouvelle valeur du bit (0 ou 1)
# Sortie : Variable avec le bit n qui vaut v.

def set_bit(x, n, v):
    return (x & ~(2**n)) | ((2**n)*v)
Bon, j'ai mis plein de parenthèses pour faciliter la lecture, même si tu ne les aimes pas trop.
Mais curieusement, je sens qu'il y a moyen de faire beaucoup plus futé…

>>> bin(42)
'0b101010'
>>> set_bit(42, 4, 1)
58
>>> bin(set_bit(42, 4, 1))
'0b111010'

hum

Sir Na Kraïou · Le 28/11/2010, à 01:23

Pylades · Le 28/11/2010, à 01:27

???

Ce n'était pas ça que tu voulais ? Donne des exemples, parce que sinon je ne vois pas…

↓ Édit : ah, donc c'est bon, en fait ? ↓

Dernière modification par Pylade (Le 28/11/2010, à 01:29)

grim7reaper · Le 28/11/2010, à 01:28

@Кຼزດ : qu'est ce qu'on doit comprendre dans ton message ?
@Pylade : non rien, j'ai dis des conneries ton truc est juste (« pourri » mais juste ), j'avais pas les yeux en face des trous c'est tout.

Dernière modification par grim7reaper (Le 28/11/2010, à 01:36)

Кຼزດ · Le 28/11/2010, à 01:30

grim7reaper a écrit :

@Кຼزດ : qu'est ce qu'on doit comprendre dans ton message ?

Ben je sais pas si j'ai bien compris ce que tu demandes, mais d'après moi, si on met le bit qui est en position 4 en partant de 0, de 101010, à 1, ça reste inchangé.

grim7reaper · Le 28/11/2010, à 01:32

Кຼزດ a écrit :

grim7reaper a écrit :
@Кຼزດ : qu'est ce qu'on doit comprendre dans ton message ?
Ben je sais pas si j'ai bien compris ce que tu demandes, mais d'après moi, si on met le bit qui est en position 4 en partant de 0, de 101010, à 1, ça reste inchangé.

Bah non, c'est bon

1 0 1 0 1 0 => 1 1 1 0 1 0
5 4 3 2 1 0 => 5 4 3 2 1 0

Donc il a bien modifié le bit 4.

Dernière modification par grim7reaper (Le 28/11/2010, à 01:34)

Кຼزດ · Le 28/11/2010, à 01:33

grim7reaper a écrit :

Кຼزດ a écrit :
grim7reaper a écrit :
@Кຼزດ : qu'est ce qu'on doit comprendre dans ton message ?
Ben je sais pas si j'ai bien compris ce que tu demandes, mais d'après moi, si on met le bit qui est en position 4 en partant de 0, de 101010, à 1, ça reste inchangé.
Bah non, c'est bon
1 0 1 0 1 0 => 1 1 1 0 1 0
5 4 3 2 1 0 => 5 4 3 2 1 0
Donc il a bien modifié le bit 4.

Ah oui, dans ce sens là… ><

grim7reaper · Le 28/11/2010, à 01:34

Oui j'aurais dû préciser qu'on comptait à partir du LSB, ça me semblait logique mais apparemment c'était ambigu.

Кຼزດ · Le 28/11/2010, à 01:35

grim7reaper a écrit :

Oui j'aurais dû préciser qu'on comptait à partir du LSB, ça me semblait logique mais apparemment c'était ambigu.

Non non, en y pensant ça paraît logique, j'ai juste trop tendance à penser en tant que tableau classique

Dernière modification par Кຼزດ (Le 28/11/2010, à 02:22)

gnuuat · Le 28/11/2010, à 01:48

grim7reaper a écrit :

Écrivez le corps de la fonction (je vous fournis le prototype) qui positionne à 1 ou à 0 le bit n de la variable entière non-signé x.
Le but étant d'avoir la fonction la plus rapide et la plus petite possible (i.e qui a le moins d'instructions).
/**
 *     Fonction : unsigned int set_bit(unsigned int x, unsigned int n, unsigned int v)
 * Description : Positionne à v le bit n de la variable x
 *
 * x : variable à modifier.
 * n : position du bit à modifier (on commence a 0).
 * v : nouvelle valeur du bit (0 ou 1)
 * Sortie : Variable avec le bit n qui vaut v.
 */
unsigned int set_bit(unsigned int x, unsigned int n, unsigned int v)
{
    /* À vous de jouer ! */
}
Pas besoin de vérifier si v vaut 0 ou 1, ni de vérifier la validité de n.

#include <limits.h>

/**
 *     Fonction : unsigned int set_bit(unsigned int x, unsigned int n, unsigned int v)
 * Description : Positionne à v le bit n de la variable x
 *
 * x : variable à modifier.
 * n : position du bit à modifier (on commence a 0).
 * v : nouvelle valeur du bit (0 ou 1)
 * Sortie : Variable avec le bit n qui vaut v.
 */
unsigned int set_bit(unsigned int x, unsigned int n, unsigned int v)
{
    unsigned int mask;

    mask = ((v == 0) ? UINT_MAX - 1 : 1);
    while (--n > 0)
        mask <<= 1;
    if (v == 0)
        return (x & mask);
    return (x ^ mask);
}

Pas le temps de regarder les implémentations déjà faites. Je pense qu'il y a plus rapide, mais a priori ça a l'air d'être fonctionnel comme ça...

grim7reaper · Le 28/11/2010, à 01:54

@gnuuat : Oulala, tu nous sors la grosse artillerie là (un truc fonctionnel c'est simple, le but c'est d'avoir un truc court ).

Petite comparaison entre ta solution et la mienne.
En mode O0 : 24 instructions pour moi, 27 pour toi.
En mode O2 : 11 instructions pour moi, 23 pour toi.

Même en premier jet, je n'aurais pas fait un truc comme ça. C'est quoi le principe de ton algo ?

@Pylade : Bon alors, tu es près du but et tu as fait le plus dur donc tu vas bien me proposer la bonne solution avant 3h, nan ?
(j'ai vérifié, Python a ce qu'il faut pour bien le faire)

Edit : nombre d'instructions mis à jour selon le second algo de gnuuat

Dernière modification par grim7reaper (Le 28/11/2010, à 02:01)

gnuuat · Le 28/11/2010, à 01:55

Arf, n commence à 0...

#include <limits.h>

/**
 *     Fonction : unsigned int set_bit(unsigned int x, unsigned int n, unsigned int v)
 * Description : Positionne à v le bit n de la variable x
 *
 * x : variable à modifier.
 * n : position du bit à modifier (on commence a 0).
 * v : nouvelle valeur du bit (0 ou 1)
 * Sortie : Variable avec le bit n qui vaut v.
 */
unsigned int set_bit(unsigned int x, unsigned int n, unsigned int v)
{
    unsigned int mask;

    mask = ((v == 0) ? UINT_MAX - 1 : 1);
    while (n-- > 0)
        mask <<= 1;
    if (v == 0)
        return (x & mask);
    return (x ^ mask);
}

Edit :
Mon algo ?
on veut deux types de masques :

un masque plein de 1 avec un 0 pour faire un ET logique (pour changer le bit à 0) ;
un masque plein de 0 avec un 1 pour faire un OU EXCLUSIF logique (pour changer le bit à 1).

Du coup, soit je pars du masque 11111111111...0, soit du masque 000000....1, je cale le bit au bon endroit, puis je fais un ET ou un OU EXCLUSIF.
C'est peut être lourd, mais au moins ce sera une solution différente (et je vais dormir, ton histoire m'a fait me coucher 1h plus tard que prévu, merci pour le point supplémentaire ).

Dernière modification par gnuuat (Le 28/11/2010, à 02:01)

grim7reaper · Le 28/11/2010, à 02:03

On peut s'en sortir sans if ni while, mais c'est vrai que ton post permet de voir une autre approche .

gnuuat · Le 28/11/2010, à 02:04

grim7reaper a écrit :

Petite comparaison entre ta solution et la mienne.
En mode O0 : 24 instructions pour moi, 27 pour toi.
En mode O2 : 11 instructions pour moi, 23 pour toi.
Edit : nombre d'instructions mis à jour selon le second algo de gnuuat

C'est juste une post-décrémentation au lieu d'une ante-décrémentation .
Je me souviens plus du premier nombre d'instructions, c'était combien ?

Edit : je changerai pas l'algo, parce que je pense venir avec un autre code demain... Si j'ai pas la flemme.

Dernière modification par gnuuat (Le 28/11/2010, à 02:04)

grim7reaper · Le 28/11/2010, à 02:07

gnuuat a écrit :

grim7reaper a écrit :
Petite comparaison entre ta solution et la mienne.
En mode O0 : 24 instructions pour moi, 27 pour toi.
En mode O2 : 11 instructions pour moi, 23 pour toi.
Edit : nombre d'instructions mis à jour selon le second algo de gnuuat
C'est juste une post-décrémentation au lieu d'une ante-décrémentation .
Je me souviens plus du premier nombre d'instructions, c'était combien ?

Dans mes premiers nombres d'instructions il y avait des erreurs (d'où mes nombreux édits).
Donc je récapitule

Version 1 :
O0 : 25 instructions
O2 : 23 instructions

Version 2 :
O0 : 27 instructions
O2 : 23 instructions

Edit : je changerai pas l'algo, parce que je pense venir avec un autre code demain... Si j'ai pas la flemme.

Et si Pylade ne trouve pas avant

Dernière modification par grim7reaper (Le 28/11/2010, à 02:08)

Pylades · Le 28/11/2010, à 02:17

Bon, je crois que là c'est vraiment optimisé.

/**
 *     Fonction : unsigned int set_bit(unsigned int x, unsigned int n, unsigned int v)
 * Description : Positionne à v le bit n de la variable x
 *
 * x : variable à modifier.
 * n : position du bit à modifier (on commence a 0).
 * v : nouvelle valeur du bit (0 ou 1)
 * Sortie : Variable avec le bit n qui vaut v.
 */
unsigned int set_bit(unsigned int x, unsigned int n, unsigned int v)
{
    return x & ~(1<<n) | v<<n;
}

Et pour te faire plaisir, il n'y a pas de parenthèses inutiles.

grim7reaper · Le 28/11/2010, à 02:23

Et nous avons un vainqueur \o/ (et en plus il est revenu au C \o/)

J'ai beau ne pas aimer les parenthèses, j'en aurais quand même mis quelques unes en plus ici

Dernière modification par grim7reaper (Le 28/11/2010, à 03:02)

nesthib · Le 28/11/2010, à 03:00

plop

Pylades · Le 28/11/2010, à 03:11

grim7reaper a écrit :

Et nous avons un vainqueur \o/ (et en plus il est revenu au C \o/)

J'ai fait le premier en Python juste pour **.

grim7reaper a écrit :

J'ai beau ne pas aimer les parenthèses, j'en aurais quand même mis quelques unes en plus ici

Pourquoi ? Pour la lisibilité ?

Ubuntu-fr

Navigation

Liens de recherche

Annonce

#1726 Le 27/11/2010, à 07:42

Re : /* Topic des codeurs couche-tard [2] */

#1727 Le 28/11/2010, à 00:20

Re : /* Topic des codeurs couche-tard [2] */

#1728 Le 28/11/2010, à 00:50

Re : /* Topic des codeurs couche-tard [2] */

#1729 Le 28/11/2010, à 01:02

Re : /* Topic des codeurs couche-tard [2] */

#1730 Le 28/11/2010, à 01:15

Re : /* Topic des codeurs couche-tard [2] */

#1731 Le 28/11/2010, à 01:19

Re : /* Topic des codeurs couche-tard [2] */

#1732 Le 28/11/2010, à 01:21

Re : /* Topic des codeurs couche-tard [2] */

#1733 Le 28/11/2010, à 01:23

Re : /* Topic des codeurs couche-tard [2] */

#1734 Le 28/11/2010, à 01:27

Re : /* Topic des codeurs couche-tard [2] */

#1735 Le 28/11/2010, à 01:28

Re : /* Topic des codeurs couche-tard [2] */

#1736 Le 28/11/2010, à 01:30

Re : /* Topic des codeurs couche-tard [2] */

#1737 Le 28/11/2010, à 01:32

Re : /* Topic des codeurs couche-tard [2] */

#1738 Le 28/11/2010, à 01:33

Re : /* Topic des codeurs couche-tard [2] */

#1739 Le 28/11/2010, à 01:34

Re : /* Topic des codeurs couche-tard [2] */

#1740 Le 28/11/2010, à 01:35

Re : /* Topic des codeurs couche-tard [2] */

#1741 Le 28/11/2010, à 01:48

Re : /* Topic des codeurs couche-tard [2] */

#1742 Le 28/11/2010, à 01:54

Re : /* Topic des codeurs couche-tard [2] */

#1743 Le 28/11/2010, à 01:55

Re : /* Topic des codeurs couche-tard [2] */

#1744 Le 28/11/2010, à 02:03

Re : /* Topic des codeurs couche-tard [2] */

#1745 Le 28/11/2010, à 02:04

Re : /* Topic des codeurs couche-tard [2] */

#1746 Le 28/11/2010, à 02:07

Re : /* Topic des codeurs couche-tard [2] */

#1747 Le 28/11/2010, à 02:17

Re : /* Topic des codeurs couche-tard [2] */

#1748 Le 28/11/2010, à 02:23

Re : /* Topic des codeurs couche-tard [2] */

#1749 Le 28/11/2010, à 03:00

Re : /* Topic des codeurs couche-tard [2] */

#1750 Le 28/11/2010, à 03:11

Re : /* Topic des codeurs couche-tard [2] */

Pied de page des forums