Voici une question qui traite de l'algorithme et de l'opération XOR du Bitwise.
Nous sommes donnés x1 * x2 * x3 * .... * xn = p , où l'opération STAR ( * ) représente XOR (BitWise) Les opérations et (x1 + A1 ) * (x2 + a2) * (x3 + a3) * .... * (xn + a) = 0 . '+' représente une opération d'addition normale.
3 Réponses :
Se référant à mon commentaire - avec une question pas encore répondue:
AI négatif semble être nécessaire: pour le cas n = 1, a1 = -x1 est la solution au problème. Je suppose donc que les AI négatifs sont également autorisés dans le cas général.
Puis, pour n = 2, il n'y a pas de solution ("min") du tout, à part le fait, il y a une limite à ce que les nombres (négatifs) peuvent être représentés dans l'ordinateur:
pour n = 2 SET: A1 = x2 + k et A2 = x1 + k. Ces rendements:
(x1 + x2 + k) xor (x2 + x1 + k) = 0, indépendamment de k
la somme (A1 + A2) = (x1 + x2 + 2 * k)
Il n'y a pas de solution minimale: nous pouvons faire k toujours plus négatif.
De même pour N> 2: Pour N Même, faites des "solutions" de paire-sage comme pour n = 2 (avec des k arbitraires); Pour n impair, célibataire, sortez-le comme pour n = 1 - et le N-1 restant est traité comme pour même n.
Dans tous les cas, vous construisez zéro xor zéro xor zéro ... = zéro, où zéro est toujours une paire de type (am = xm + 1 + k; am + 1 = xm + k), sauf lorsque N est impair, où vous avez un autre facteur, c'est-à-dire du type {am = -xm) . Sauf pour n = 1, les solutions peuvent devenir aussi grandes négatives que vous le souhaitez.
Hm, donc pour même n, il est une solution
Dans un sens, oui, vous êtes bien sûr bien sûr (et cela s'applique également à Odd N> 2, ajustant les K pour appuyer sur la somme négative à la limite représentant), mais je suppose que ce n'est pas le type de solution L'ask à la recherche de ...
HM, donc pour même N, une solution toujours existe, même si l'A [I] doit être positif. La question devient donc (pour même n seulement!) Si un [i] = x [1] + ... + x [I-1] + x [i] + ... + x [n] est la solution minimale . Pour N = 1, je suis d'accord qu'il n'y a pas de solution avec A1> = 0, à moins que vous ne perdiez le débordement se produise. Je ne suis cependant pas convaincu que la même chose est vraie pour N> 1, n impair. Qui a dit que vous ne pouvez pas trouver un impair nombre d'entiers yi avec yi> = xi et y1 * ... * yn = 0?
Je viens de réaliser qu'un [i] = x [1] + ... + x [i-1] + x [i] + ... + x [n] est définitivement pas le minimal Solution pour N. SIMPD N. Faire deux paires adjacentes de (x [i] + a [i]) s'annule, c'est-à-dire un [i] = {x [i-1] si je suis impair , X [I + 1] Si je suis même}, produira généralement une solution plus petite. Pour N, x0 + ... + xn est donc une liaison pour A0 + ... + an.
Pour N Même, imposant l'exigence d'AI positive, vous obtenez un minimum inférieur à votre général {A (i) = somme (tous x (j)) - x (i)}, par jumelage, dans la mesure de ma réponse. Un premier coup serait de trier le x (i), puis un ensemble par couple jumère {A (i) = (x (j) - (x (i)); a (j) = 0}. Le résultat est la somme de la Différences par paires (x (J) - (x (i)). BTW, je pense que nous devrions également attendre une réponse de la personne qui posa la question, de clarifier ce qui est requis / autorisé.
Vrai. Cette approche peut être généralisée à N = 3, je pense. Trier les xi comme vous le faites. Puis choisissez un Y3 qui est plus grand que x3. Nous devons maintenant trouver Y1, Y2 de telle que Y1> = x1, Y2> = x2 et Y1 * Y2 = Y3. Depuis Y1 * Y2 == Y1 | Y2 Si Y1 & Y2 = 0, vous pouvez par exemple définir Y1 = Y3 & 1 ... 0101B et Y2 = Y3 & 1 ... 010b (c'est-à-dire, utilisez les morceaux même pour y1 et l'impair bits pour y2). Si cela ne satisfait pas y1> = x1 ou y2> = x2, choisissez simplement une plus grande Y3. Ensuite, définissez simplement un [i] = y [i] -x [i]. Ensemble avec la solution pour même N, cela montre qu'une solution existe toujours pour N> 1. La question de la minimalité est toujours ouverte, cependant.
Je suis d'accord que vous êtes une suggestion originale, c'est-à-dire que pour N> 2 A SIMILY XOR-RÉSULTURE est possible avec un (i) positif uniquement, est correct en général (contrairement à ma première "HUNCH"). Le montrant pour N = 3 suffit, comme pour les N> 4, nous avons déjà une approche pour les "paires restantes" après avoir dissipé un triplé pour "traitement spécial".
J'ai trouvé une autre généralisation à N> = 2 en partant d'une version généralisée de l'affaire N = 2 où le côté droit peut être un entier arbitraire, pas nécessairement 0. Je l'ai mis dans une réponse distincte pour mieux lisibilité.
@Berttevelde Tous les entiers sont non négatifs! Donc, aussi tous les AI sont> = 0
Le problème peut être retraité comme le problème suivant de la BIP (programmation linéaire entier). p>
a1=1, a2=1, a3=0
Tous les entiers sont non négatifs! Donc, aussi tous les AI sont> = 0
@ user1708762 yup, je pensais que. Ma réponse ne produit que des AI> = 0. Sinon, il est trivial de voir qu'une solution existe toujours, vient de définir AI = -Xi.
Peut-être un premier intérêt au minimum - N> 1, tout a (i) positif - est le long des lignes suivantes. Laissez-moi d'abord indiquer une certaine terminologie.
initialiser y (i) = x (i); Y (i) signifie (x (i) + a (i)), donc nous initialisons en fait A (i) = 0 (pour i = 1..n). De même, définir q = y (1) ^ y (2) ^ ... ^ y (n) (^ signifie XOR); Initialement q = p. p>
Nous allons ajusterons le y (i) pour faire q zéro, préserver toujours y (i)> = x (i) - c'est-à-dire: a (i)> = 0. p>
considérer pour chaque nombre (x, y, a, p, q) son expansion binaire (bit-), numérotant les bits par m = 0,1,2, ..: bit m représente le 2 ** m pièce de valeur dans le numéro. p>
Notez qu'un bit n'est pas zéro dans q si et seulement si le nombre de y (i) qui ont le même bit non-zéro est impair. P >
procéder comme suit. Scannez les bits incriminés (valeur 1) dans Q, de haut en bas, c'est-à-dire: commençant par le bit le plus élevé ('actuellement restant ») 1. Laissez-le être bit #m. P>
Nous avons deux cas : P>
Case A. Il y a au moins un y (i) qui a un zéro à bit m. Définissez C comme la collection de tous ces y (i). P>
Nous allons choisir un de ceux-ci (voir ci-dessous) et définir son m-bit sur 1, c'est-à-dire changer P>
INCREMENT1 as (2**k - 2**m) and set INCREMENT2 = 2**k.
Sont
xi entiers positifs, ou peuvent-ils aussi être négatifs?@IVLAD Tous les entiers sont positifs.
Je pense que plus de détails sont nécessaires. Quelles sont les limites sur
ai ? Doit-ils aussi être positif? Quelle est leur taille?@IVLAD Tous les entiers sont non négatifs! Donc, aussi tous les AI sont> = 0
@ user1708762 Avez-vous réussi à résoudre le problème sous la condition de minimalité?