{"id":1160,"date":"2026-04-06T22:51:59","date_gmt":"2026-04-06T22:51:59","guid":{"rendered":"https:\/\/yesrenee.com\/?p=1160"},"modified":"2026-04-07T22:28:45","modified_gmt":"2026-04-07T22:28:45","slug":"xor","status":"publish","type":"post","link":"https:\/\/yesrenee.com\/?p=1160","title":{"rendered":"XOR"},"content":{"rendered":"\n

XOR<\/a>, also known as Exclusive OR, is a logical operation often used in programming. It is referred to $\\oplus$, but in programming, for simplicity, it is referred to as $^$.<\/p>\n\n\n\n

There are many special propreties about XOR:<\/p>\n\n\n\n

The order in which you calculate XOR operations does not matter, for example, $2^3^1^4$ can also be calculated as $1^2^4^2$.<\/p>\n\n\n\n

If you have some numbers, divide them into any number of groups, and find their XOR’s in each group, and find the total sum:<\/p>\n\n\n\n

You can find a max or a min answer, the max answer is if you added them all (we split each number as an individual group), and the min answer is if you didn’t split anything<\/em> and XOR’d it all.<\/p>\n\n\n\n

Additionally, if you had two numbers $L$ and $R$, and wanted to find their XOR from L to R, inclusive: meaning, for example, if L were 2 and R were 5, you’d have to find $2^3^4^5$.<\/p>\n\n\n\n

If you implemented this in coding, you could get TLE due to large inputs. It could, however, be fixed with this proprety:
<\/p>\n\n\n\n

$XOR(L\u00a0to\u00a0R)=XOR(0\u00a0to\u00a0R)\u2295XOR(0\u00a0to\u00a0L\u22121)$<\/p>\n\n\n\n

That does not sound very time-efficient, right?<\/p>\n\n\n\n

The key XOR property of consecutive numbers<\/strong> is about how XOR behaves over ranges like0<\/mn>\u2295<\/mo>1<\/mn>\u2295<\/mo>2<\/mn>\u2295<\/mo>\u22ef<\/mo>\u2295<\/mo>n<\/mi><\/mrow>0 \\oplus 1 \\oplus 2 \\oplus \\cdots \\oplus n<\/annotation><\/semantics><\/math>This pattern repeats every 4 numbers:If <\/mtext>n<\/mi>\u200a<\/mtext>m<\/mi>o<\/mi>d<\/mi><\/mrow><\/mo>\u200a<\/mtext>4<\/mn>=<\/mo>0<\/mn><\/mrow><\/mstyle><\/mtd><\/mrow>\u21d2<\/mo>result<\/mtext>=<\/mo>n<\/mi><\/mrow><\/mstyle><\/mtd><\/mtr>If <\/mtext>n<\/mi>\u200a<\/mtext>m<\/mi>o<\/mi>d<\/mi><\/mrow><\/mo>\u200a<\/mtext>4<\/mn>=<\/mo>1<\/mn><\/mrow><\/mstyle><\/mtd><\/mrow>\u21d2<\/mo>result<\/mtext>=<\/mo>1<\/mn><\/mrow><\/mstyle><\/mtd><\/mtr>If <\/mtext>n<\/mi>\u200a<\/mtext>m<\/mi>o<\/mi>d<\/mi><\/mrow><\/mo>\u200a<\/mtext>4<\/mn>=<\/mo>2<\/mn><\/mrow><\/mstyle><\/mtd><\/mrow>\u21d2<\/mo>result<\/mtext>=<\/mo>n<\/mi>+<\/mo>1<\/mn><\/mrow><\/mstyle><\/mtd><\/mtr>If <\/mtext>n<\/mi>\u200a<\/mtext>m<\/mi>o<\/mi>d<\/mi><\/mrow><\/mo>\u200a<\/mtext>4<\/mn>=<\/mo>3<\/mn><\/mrow><\/mstyle><\/mtd><\/mrow>\u21d2<\/mo>result<\/mtext>=<\/mo>0<\/mn><\/mrow><\/mstyle><\/mtd><\/mtr><\/mtable>\\begin{aligned} \\text{If } n \\bmod 4 = 0 &\\Rightarrow \\text{result} = n \\\\ \\text{If } n \\bmod 4 = 1 &\\Rightarrow \\text{result} = 1 \\\\ \\text{If } n \\bmod 4 = 2 &\\Rightarrow \\text{result} = n + 1 \\\\ \\text{If } n \\bmod 4 = 3 &\\Rightarrow \\text{result} = 0 \\end{aligned}<\/annotation><\/semantics><\/math><\/p>\n\n\n\n

<\/p>\n\n\n\n

<\/p>\n\n\n\n

P.S. if you have no idea why you’re WA’ing, did you use long long int?<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

XOR, also known as Exclusive OR, is a logical operation often used in programming. It is referred to $\\oplus$, but in programming, for simplicity, it is referred to as $^$. There are many special propreties about XOR: The order in which you calculate XOR operations does not matter, for example, $2^3^1^4$ can also be calculated […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[47,46,45,48],"class_list":["post-1160","post","type-post","status-publish","format-standard","hentry","category-daily","tag-ccc","tag-coding","tag-pre-contest-review","tag-vocabulary"],"_links":{"self":[{"href":"https:\/\/yesrenee.com\/index.php?rest_route=\/wp\/v2\/posts\/1160","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/yesrenee.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/yesrenee.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/yesrenee.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/yesrenee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1160"}],"version-history":[{"count":7,"href":"https:\/\/yesrenee.com\/index.php?rest_route=\/wp\/v2\/posts\/1160\/revisions"}],"predecessor-version":[{"id":1167,"href":"https:\/\/yesrenee.com\/index.php?rest_route=\/wp\/v2\/posts\/1160\/revisions\/1167"}],"wp:attachment":[{"href":"https:\/\/yesrenee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1160"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/yesrenee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1160"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/yesrenee.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1160"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}