Formule directe pour sommer XOR

Question

J'ai des nombres XOR de 1 à N, existe-t-il une formule directe pour cela?

Par exemple, si N = 6 puis 1^2^3^4^5^6 = 7 je veux le faire sans utiliser la boucle donc je besoin d'un O (1) formule (le cas échéant)

Answer 1

Essayez ceci:

le bit LSB obtient basculée chaque fois que le N est impair, donc nous pouvons dire que

rez & 1 == (N & 1)^((N >> 1) & 1) 

Le même modèle peut être observé pour le reste des bits. Chaque fois que les bits B et B+1 (à partir de LSB) dans N seront différents, le bit B dans le résultat doit être défini.

Ainsi, le résultat final sera (y compris N): rez = N^(N >> 1)

EDIT: désolé, il a eu tort. la bonne réponse:

pour impair N: rez = (N^(N >> 1)) & 1

même pour N: rez = (N & ~1) | ((N^(N >> 1)) & 1)

Answer 2

modifier
GSerg a affiché une formule sans boucles, mais supprimé pour une raison quelconque (undeleted maintenant). La formule est parfaitement valide (sauf une petite erreur). Voici la version C++.

if n % 2 == 1 { 
    result = (n % 4 == 1) ? 1 : 0; 
} else { 
    result = (n % 4 == 0) ? n : n + 1; 
} 

On peut le prouver par induction, vérifier tous les rappels de division par 4. Bien, aucune idée de comment vous pouvez arriver avec cela sans générer de sortie et de voir la régularité.

Veuillez expliquer votre approche un peu plus.
Étant donné que chaque bit est indépendant en mode xor, vous pouvez les calculer séparément.
En outre, si vous regardez k-th bit du numéro 0..n, il va former un motif. Par exemple, les nombres de 0 à 7 sous forme binaire.

000 
001 
010 
011 
100 
101 
110 
111 

Vous voyez que pour le bit k-ième (k commence à 0), il es 2^k, 2^k les zéros, puis à nouveau 2^k zéros, etc.
Par conséquent, vous pouvez pour chaque bit de calculer le nombre ceux qui sont sans passer par tous les nombres de 1 à n. Par exemple, pour k = 2, il y a des blocs répétés de 2^2 == 4 zéros et de ceux qui sont . Ensuite,

int ones = (n/8) * 4; // full blocks 
if (n % 8 >= 4) { // consider incomplete blocks in the end 
    ones += n % 8 - 3; 
} 

Answer 3

permet de dire que la fonction XOR toutes les valeurs de 1 à N être XOR (N), puis

 
XOR(1) = 000 1 = 0 1 (The 0 is the dec of bin 000) 
XOR(2) = 001 1 = 1 1 
XOR(3) = 000 0 = 0 0 
XOR(4) = 010 0 = 2 0 
XOR(5) = 000 1 = 0 1 
XOR(6) = 011 1 = 3 1 
XOR(7) = 000 0 = 0 0 
XOR(8) = 100 0 = 4 0 
XOR(9) = 000 1 = 0 1 
XOR(10)= 101 1 = 5 1 
XOR(11)= 000 0 = 0 0 
XOR(12)= 110 0 = 6 0 

J'espère que vous pouvez voir le modèle. Il devrait être similaire pour d'autres nombres aussi.

Answer 4

Pour impair N, le résultat est soit 10 ou (cyclique, 0 pour N=3, 1 pour N=5, 0 pour N=7 etc.)

Pour encore N, le résultat est soit N ou N+1 (cyclique, N + 1 pour N=2, N pour N=4, N + 1 pour N=6, N pour N=8 etc.).

pseudocode:

if (N mod 2) = 0 
    if (N mod 4) = 0 then r = N else r = N+1 
else 
    if (N mod 4) = 1 then r = 1 else r = 0 

Answer 5

Votre formule est N & (N % 2 ? 0 : ~0) | (((N & 2)>>1)^(N & 1)):

int main() 
{ 
    int S = 0; 
    for (int N = 0; N < 50; ++N) { 
     S = (S^N); 
     int check = N & (N % 2 ? 0 : ~0) | (((N & 2)>>1)^(N & 1)); 
     std::cout << "N = " << N << ": " << S << ", " << check << std::endl; 
     if (check != S) throw; 
    } 

    return 0; 
} 

sortie:

N = 0: 0, 0    N = 1: 1, 1    N = 2: 3, 3 
N = 3: 0, 0    N = 4: 4, 4    N = 5: 1, 1 
N = 6: 7, 7    N = 7: 0, 0    N = 8: 8, 8 
N = 9: 1, 1    N = 10: 11, 11   N = 11: 0, 0 
N = 12: 12, 12   N = 13: 1, 1   N = 14: 15, 15 
N = 15: 0, 0   N = 16: 16, 16   N = 17: 1, 1 
N = 18: 19, 19   N = 19: 0, 0   N = 20: 20, 20 
N = 21: 1, 1   N = 22: 23, 23   N = 23: 0, 0 
N = 24: 24, 24   N = 25: 1, 1   N = 26: 27, 27 
N = 27: 0, 0   N = 28: 28, 28   N = 29: 1, 1 
N = 30: 31, 31   N = 31: 0, 0   N = 32: 32, 32 
N = 33: 1, 1   N = 34: 35, 35   N = 35: 0, 0 
N = 36: 36, 36   N = 37: 1, 1   N = 38: 39, 39 
N = 39: 0, 0   N = 40: 40, 40   N = 41: 1, 1 
N = 42: 43, 43   N = 43: 0, 0   N = 44: 44, 44 
N = 45: 1, 1   N = 46: 47, 47   N = 47: 0, 0 
N = 48: 48, 48   N = 49: 1, 1   N = 50: 51, 51 

Explication:

1. Le bit bas est XOR entre le bit bas et le bit suivant.

2. Pour chaque bit sauf bit faible ce qui suit est:

   • si N est impair, alors que le bit est 0.
   • si N est même alors que le bit est égal à peu correspondu de N.

Ainsi, pour le cas de N impair le résultat est toujours 0 ou 1.

Answer 6

Grande answe par Alexey Malistov! Une variante de sa formule: n & 1 ? (n & 2) >> 1^1 : n | (n & 2) >> 1 ou de manière équivalente n & 1 ? !(n & 2) : n | (n & 2) >> 1.

Answer 7

cette méthode évite d'utiliser conditionals F(N)=(N&((N&1)-1))|((N&1)^((N&3)>>1)

F(N)= (N&(b0-1)) | (b0^b1) 

Si vous regardez le XOR des premiers chiffres que vous obtenez:

N  | F(N) 
------+------ 
0001 | 0001 
0010 | 0011 
0011 | 0000 
0100 | 0100 
0101 | 0001 
0110 | 0111 
0111 | 0000 
1000 | 1000 
1001 | 0001 

Espérons que vous remarquerez que le motif:

si N mod 4 = 1 que F(N)=1
si N mod 4 = 3 que F(N)=0
si N mod 4 = 0 que F(N)=N
si N mod 4 = 2 que F(N)=N mais avec le premier bit comme 1 si N|1

la partie la plus délicate devient ce dans une déclaration sans conditionals mal expliquer la logique je pour faire ça.

prendre les 2 premiers bits significatifs de N appeler:

b0 et b1 et ceux-ci sont obtenus avec:

b0 = N&1 
b1 = N&3>>1 

Notez que si b0 == 1 nous devons 0 tous les bits, mais si ce n'est pas tous les bits, sauf pour le premier bit restent les mêmes. Nous pouvons faire ce comportement:

N & (b0-1): cela fonctionne en raison du complément de 2, -1 est égal à un nombre avec tous les bits à 1 et 1-1=0 donc quand b0=1 il en résulte F(N)=0 .. Telle est donc la première partie de la fonction:

F(N)= (N&(b0-1))... 

maintenant cela fonctionne pour pour N mod 4 == 3 et 0, pour les 2 autres cas permet de regarder uniquement à b1, b0 et F(N)0:

b0|b1|F(N)0 
--+--+----- 
1| 1| 0 
0| 0| 0 
1| 0| 1 
0| 1| 1 

En espérant que cette table de vérité semble familière! c'est b0 XOR b1 (b1^b0). Maintenant que nous savons comment obtenir le dernier bit laisser mettre que sur notre fonction:

F(N)=(N&(b0-1))|b0^b1 

et là vous allez, une fonction sans utiliser conditionals. cela est également utile si vous voulez calculer le XOR à partir des nombres positifs a à b. vous pouvez faire: F(a) XOR F(b).

Answer 8

Jetez un coup d'oeil à ceci. Cela va résoudre votre problème.

https://stackoverflow.com/a/10670524/4973570

Pour calculer la somme XOR de 1 à N:

int ans,mod=N%4; 
if(mod==0) ans=N; 
else if(mod==1) ans=1; 
else if(mod==2) ans=N+1; 
else if(mod==3) ans=0; 

Answer 9

Avec changement minimum à la logique originale:

int xor = 0; 
for (int i = 1; i <= N; i++) { 
    xor ^= i; 
} 

Nous pouvons avoir:

int xor = 0; 
for (int i = N - (N % 4); i <= N; i++) { 
    xor ^= i; 
} 

Il a une boucle mais il faudrait un temps constant pour l'exécuter. Le nombre de fois que nous parcourons la boucle for varierait entre 1 et 4.

Answer 10

Que pensez-vous de cela?

!(n&1)*n+(n%4&n%4<3) 

Answer 11

Si encore quelqu'un dont il a besoin solution python ici simple:

def XorSum(L): 
    res = 0   
    if (L-1)%4 == 0: 
     res = L-1 
    elif (L-1)%4 == 1: 
     res = 1 
    elif (L-1)%4 == 2: 
     res = (L-1)^1 
    else: #3 
     res= 0 
    return res 

Answer 12

Cela fonctionne très bien sans aucun problème pour tout n;

int xorn(int n) 
{ 

    if (n % 4 == 0) 
     return n; 
    else if(n % 4 == 1) 
     return 1; 
    else if(n % 4 == 2) 
     return n+1; 
    else 
     return 0; 
}