Operation binaire

Enfin j'ai tout de même toujours pas compris xD

Je comprend les maths, mais après.. :x

Je ne saurais pas l'expliquer avec les bons termes, mais en gros il suffit de combiner les valeurs avec l'opérateur AND, puis de calculer le XOR du resultat avec les valeurs de départ (je ne suis pas très clair, désolé) :

1
2
3
4
5
6
7

resultat = première valeur

pour chaque valeur suivante faire:
    resultat = resultat AND valeur

pour chaque valeur (depuis la première) faire:
    resultat = resultat XOR valeur

En C, ça pourrait ressembler à quelque chose comme ça, je crois :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int funct(int array[], int length) {

    int result, index;

    if(length < 2)
        return 0;

    result = array[0];
    for(index = 1; index < length; ++index)
        result &= array[index]; // array[0] AND ... AND array[length-1]

    for(index = 0; index < length; ++index)
        result ^= array[index]; // result XOR array[0] XOR ... XOR array[length-1]

    return result
}

Hum … Ca marche pas cette formule.
{1, 1, 1} et {1, 1, 1, 1} ne vont pas donner le même résultat.

C'est ce qui me semblait En fait faut le faire en une seule opération j'ai l'impression… (si l'on suit ce qui a été dit avant)

Tu as zappé la solution incrémentale que j'ai donnée, avec démonstration dans une feuille de calcul de google drive ?

C'est la façon de faire la plus intuitive pour nous. Après il doit y avoir moyen de faire des optims qui vont vite devenir non maintenables.

Ouia justement ! En fait j'ai pas siper bien compris les operatoons que tu faisais..

OK, les cours de maths à l'école n'ont quand même pas tant changé que cela en 25ans… As-tu déjà vu des séries ?

On les initialise à quelque chose (ici, Masque[0] et Resultat[0] sont initialisés à 0), et on exprime M[i] en fonction de M[i-1] et R[i-1] et Input[i], et on exprime R[i] en fonction de M[i], I[i] et R[i-1]. Ce qui fait que de façon incrémentale, à chaque fois que l'on rajoute un nombre en entrée (I[i+1]), on est capable de calculer le résultat de l'opération sur tous les I de 1 à i+1 à partir du résultat sur I[de 1 à i], et d'un masque qui est mis à jour à chaque nouveau nombre.

On alors c'est les manipulations binaires qui te sont moins intuitives ? (les notions de masquage et de mémorisation sont employées dans l'algo que je propose)

NB: le masque sert à mémoriser les bits pour lesquels on a détecté plus d'un 1.

Expliqué comme ca je comprend mieux

En fait ce sont des suites et non des series (qui sont autre chose), mais j'ai compris maintenant ! La facon dont tu as expliquer ne m'avait pas fait percuter. Mais du coup, c'est simple et plutot rapide je pense ! Merci beaucoup

suite, série, c'est vieux tout ça pour moi ^^'
Cool si tu vois ce que j'avais cherché à faire.

En termes de rapidité, tout dépend du nombre d'entrées que tu vas avoir. Jusqu'à trois, la formule simplifiée donnée par simbilou (via le site de réduction des expressions booléennes me parait pas mal). Au delà, la simplification/factorisation ne donne rien de bon. La formule générale pour n entrées est la somme (ou-logique) des produits (et-logique) des négations des entrées (sauf une entrée : la i-ème de la somme qui n'est pas prise en négatif). Soit pour n entrées, il y a n(n-1) produits (booléen -> des ET), n-1 additions (booléennes -> des OU), et n négations.
La version incrémentale est en O(n). Il faut juste trouver le point d'équilibre.

Bon, j'ai essayer de faire l'implémentation aujourd'hui, sauf que je ne comprend pas à quoi correspodent R et M…

Masque à l'itération i
Résultat à itération i

D'accord.. Et c'est quoi le masque ? J'ai googler un peu mais rien trouvre de très pertinent

Donc si je veux savoir s'il n'y à qu'une occurence d'un bit à 1, il faut que je regarde résultat ? Ce sont uniquement les bits qui ont une et une seule occurence de 1, ou aussi ceux qui en ont 0 ?

Désolé mais j'ai un peu de mal à comprendre comment fonctionne la suite et la j'ai pas trop le temps, je regarderais une fois mon projet fini

Le Résultat est ce que tu attends. Le Masque est ce qui sert à le calculer. Et ce que contient le masque est expliqué (plusieurs fois il me semble) dans les messages précédents.

Le sujet est en résolu ! Merci beaucoup lmghs, grâce à toi j'ai probablement un des programmes de résolution de sudoku les plus rapide de ma promo ! J'ai mis le lien du thread en commentaire (oui je suis honnête ^^) et j'ai mis ton pseudo, en espérant que ça ne te gène pas

Je ne vois pas trop le rapport avec la résolution de sudoku pour le coup, mais tu peux me citer

NB: il existe des forums spécialisés sur le sujet, et il y a plein de choses hyper intéressantes sur le sujet. Notamment au niveaux des heuristiques et de leur application.

Parce que j'en avais besoin dans mon projet de résolution de sudoku (qui est un projet scolaire)