XOR Tricks
Editorial
Single Number, without the memory
Single Number gives you an array where every value appears twice except one, and asks for that one in linear time with constant extra space. The first idea that works is a set: add a value the first time you see it, remove it the second time, and the one left at the end is the answer. Both ways, on 1,000,001 values, in every language the judge runs:
import time
nums = list(range(500000)) + list(range(499999, -1, -1)) + [1000000] # every value twice, one once
def with_a_set(nums): # add a value the first time, remove it the second
seen, most = set(), 0
for v in nums:
if v in seen:
seen.remove(v)
else:
seen.add(v)
most = max(most, len(seen))
return seen.pop(), most
def with_xor(nums): # pairs cancel: v ^ v is 0
x = 0
for v in nums:
x ^= v
return x
start = time.perf_counter()
found, most = with_a_set(nums)
print(f"with a set: {found} in {(time.perf_counter() - start) * 1000:.1f} ms, {most} values held at once")
start = time.perf_counter()
found = with_xor(nums)
print(f"with xor: {found} in {(time.perf_counter() - start) * 1000:.1f} ms, one integer held")
# with a set: 1000000 in 122.6 ms, 500000 values held at once
# with xor: 1000000 in 24.2 ms, one integer heldimport java.util.*;
public class Main {
public static void main(String[] args) {
int[] nums = new int[1000001]; // every value twice, one once
for (int i = 0; i < 500000; i++) {
nums[i] = i;
nums[500000 + i] = 499999 - i;
}
nums[1000000] = 1000000;
long start = System.nanoTime();
Set<Integer> seen = new HashSet<>(); // add a value the first time, remove it the second
int most = 0;
for (int v : nums) {
if (!seen.remove(v)) {
seen.add(v);
most = Math.max(most, seen.size());
}
}
int found = seen.iterator().next();
System.out.printf("with a set: %d in %.1f ms, %d values held at once%n", found,
(System.nanoTime() - start) / 1e6, most);
start = System.nanoTime();
int x = 0; // pairs cancel: v ^ v is 0
for (int v : nums) x ^= v;
System.out.printf("with xor: %d in %.1f ms, one integer held%n", x, (System.nanoTime() - start) / 1e6);
}
}
// with a set: 1000000 in 150.2 ms, 500000 values held at once
// with xor: 1000000 in 6.2 ms, one integer held#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> nums; // every value twice, one once
for (int i = 0; i < 500000; i++) nums.push_back(i);
for (int i = 499999; i >= 0; i--) nums.push_back(i);
nums.push_back(1000000);
auto start = chrono::steady_clock::now();
unordered_set<int> seen; // add a value the first time, remove it the second
size_t most = 0;
for (int v : nums) {
if (!seen.erase(v)) {
seen.insert(v);
most = max(most, seen.size());
}
}
double ms = chrono::duration<double, milli>(chrono::steady_clock::now() - start).count();
printf("with a set: %d in %.1f ms, %zu values held at once\n", *seen.begin(), ms, most);
start = chrono::steady_clock::now();
int x = 0; // pairs cancel: v ^ v is 0
for (int v : nums) x ^= v;
ms = chrono::duration<double, milli>(chrono::steady_clock::now() - start).count();
printf("with xor: %d in %.1f ms, one integer held\n", x, ms);
}
// with a set: 1000000 in 50.0 ms, 500000 values held at once
// with xor: 1000000 in 0.4 ms, one integer heldconst nums = []; // every value twice, one once
for (let i = 0; i < 500000; i++) nums.push(i);
for (let i = 499999; i >= 0; i--) nums.push(i);
nums.push(1000000);
let start = performance.now();
const seen = new Set(); // add a value the first time, remove it the second
let most = 0;
for (const v of nums) {
if (!seen.delete(v)) {
seen.add(v);
most = Math.max(most, seen.size);
}
}
const found = seen.values().next().value;
console.log(`with a set: ${found} in ${(performance.now() - start).toFixed(1)} ms, ${most} values held at once`);
start = performance.now();
let x = 0; // pairs cancel: v ^ v is 0
for (const v of nums) x ^= v;
console.log(`with xor: ${x} in ${(performance.now() - start).toFixed(1)} ms, one integer held`);
// with a set: 1000000 in 211.4 ms, 500000 values held at once
// with xor: 1000000 in 25.3 ms, one integer heldconst nums: number[] = []; // every value twice, one once
for (let i = 0; i < 500000; i++) nums.push(i);
for (let i = 499999; i >= 0; i--) nums.push(i);
nums.push(1000000);
let start = performance.now();
const seen = new Set<number>(); // add a value the first time, remove it the second
let most = 0;
for (const v of nums) {
if (!seen.delete(v)) {
seen.add(v);
most = Math.max(most, seen.size);
}
}
const found = seen.values().next().value;
console.log(`with a set: ${found} in ${(performance.now() - start).toFixed(1)} ms, ${most} values held at once`);
start = performance.now();
let x = 0; // pairs cancel: v ^ v is 0
for (const v of nums) x ^= v;
console.log(`with xor: ${x} in ${(performance.now() - start).toFixed(1)} ms, one integer held`);
// with a set: 1000000 in 218.5 ms, 500000 values held at once
// with xor: 1000000 in 25.5 ms, one integer heldusing System;
using System.Collections.Generic;
using System.Diagnostics;
class Program {
static void Main() {
var nums = new List<int>(); // every value twice, one once
for (int i = 0; i < 500000; i++) nums.Add(i);
for (int i = 499999; i >= 0; i--) nums.Add(i);
nums.Add(1000000);
var watch = Stopwatch.StartNew();
var seen = new HashSet<int>(); // add a value the first time, remove it the second
int most = 0;
foreach (int v in nums) {
if (!seen.Remove(v)) {
seen.Add(v);
most = Math.Max(most, seen.Count);
}
}
int found = 0;
foreach (int v in seen) found = v;
Console.WriteLine($"with a set: {found} in {watch.Elapsed.TotalMilliseconds:F1} ms, {most} values held at once");
watch.Restart();
int x = 0; // pairs cancel: v ^ v is 0
foreach (int v in nums) x ^= v;
Console.WriteLine($"with xor: {x} in {watch.Elapsed.TotalMilliseconds:F1} ms, one integer held");
}
}
// with a set: 1000000 in 28.4 ms, 500000 values held at once
// with xor: 1000000 in 0.9 ms, one integer heldpackage main
import (
"fmt"
"time"
)
func main() {
nums := []int{} // every value twice, one once
for i := 0; i < 500000; i++ {
nums = append(nums, i)
}
for i := 499999; i >= 0; i-- {
nums = append(nums, i)
}
nums = append(nums, 1000000)
start := time.Now()
seen := map[int]bool{} // add a value the first time, remove it the second
most := 0
for _, v := range nums {
if seen[v] {
delete(seen, v)
} else {
seen[v] = true
most = max(most, len(seen))
}
}
found := 0
for v := range seen {
found = v
}
ms := float64(time.Since(start).Microseconds()) / 1000
fmt.Printf("with a set: %d in %.1f ms, %d values held at once\n", found, ms, most)
start = time.Now()
x := 0 // pairs cancel: v ^ v is 0
for _, v := range nums {
x ^= v
}
ms = float64(time.Since(start).Microseconds()) / 1000
fmt.Printf("with xor: %d in %.1f ms, one integer held\n", x, ms)
}
// with a set: 1000000 in 183.4 ms, 500000 values held at once
// with xor: 1000000 in 0.9 ms, one integer heldBoth found 1,000,000 in all seven. The set held up to 500,000 values at once; XOR held one integer, and it was also the faster of the two everywhere: 122.6 ms against 24.2 ms in Python, 150.2 ms against 6.2 ms in Java, 183.4 ms against 0.9 ms in Go. The whole trick is that a value XORed with itself is 0, so the pairs cancel and the single value is what's left. This lesson is about that cancelling, and what it can do beyond Single Number.
What XOR does
XOR compares two bits and gives 1 when they differ. Three rules follow, and every trick in this lesson uses them: a ^ a = 0, a ^ 0 = a, and the order doesn't matter, so (a ^ b) ^ c = a ^ (b ^ c) and a ^ b = b ^ a. In each column of bits, XOR keeps 1 exactly when the column has an odd number of 1s. Checking the rules, then XORing 4, 1, 2, 1 and 2 one at a time:
print(5 ^ 5, 5 ^ 0, 5 ^ 3 ^ 5, 3 ^ 5 ^ 5) # a ^ a is 0, a ^ 0 is a, and the order doesn't matter
x = 0
for v in (4, 1, 2, 1, 2):
x ^= v
print(f"after {v}: {x} ({x:03b})")
# 0 5 3 3
# after 4: 4 (100)
# after 1: 5 (101)
# after 2: 7 (111)
# after 1: 6 (110)
# after 2: 4 (100)public class Main {
public static void main(String[] args) {
// a ^ a is 0, a ^ 0 is a, and the order doesn't matter
System.out.println((5 ^ 5) + " " + (5 ^ 0) + " " + (5 ^ 3 ^ 5) + " " + (3 ^ 5 ^ 5));
int x = 0;
for (int v : new int[] {4, 1, 2, 1, 2}) {
x ^= v;
System.out.println("after " + v + ": " + x + " ("
+ String.format("%3s", Integer.toBinaryString(x)).replace(' ', '0') + ")");
}
}
}
// 0 5 3 3
// after 4: 4 (100)
// after 1: 5 (101)
// after 2: 7 (111)
// after 1: 6 (110)
// after 2: 4 (100)#include <bits/stdc++.h>
using namespace std;
int main() {
// a ^ a is 0, a ^ 0 is a, and the order doesn't matter
cout << (5 ^ 5) << " " << (5 ^ 0) << " " << (5 ^ 3 ^ 5) << " " << (3 ^ 5 ^ 5) << "\n";
int x = 0;
for (int v : {4, 1, 2, 1, 2}) {
x ^= v;
cout << "after " << v << ": " << x << " (" << bitset<3>(x) << ")\n";
}
}
// 0 5 3 3
// after 4: 4 (100)
// after 1: 5 (101)
// after 2: 7 (111)
// after 1: 6 (110)
// after 2: 4 (100)console.log(5 ^ 5, 5 ^ 0, 5 ^ 3 ^ 5, 3 ^ 5 ^ 5); // a ^ a is 0, a ^ 0 is a, and the order doesn't matter
let x = 0;
for (const v of [4, 1, 2, 1, 2]) {
x ^= v;
console.log(`after ${v}: ${x} (${x.toString(2).padStart(3, "0")})`);
}
// 0 5 3 3
// after 4: 4 (100)
// after 1: 5 (101)
// after 2: 7 (111)
// after 1: 6 (110)
// after 2: 4 (100)console.log(5 ^ 5, 5 ^ 0, 5 ^ 3 ^ 5, 3 ^ 5 ^ 5); // a ^ a is 0, a ^ 0 is a, and the order doesn't matter
let x: number = 0;
for (const v of [4, 1, 2, 1, 2]) {
x ^= v;
console.log(`after ${v}: ${x} (${x.toString(2).padStart(3, "0")})`);
}
// 0 5 3 3
// after 4: 4 (100)
// after 1: 5 (101)
// after 2: 7 (111)
// after 1: 6 (110)
// after 2: 4 (100)using System;
class Program {
static void Main() {
// a ^ a is 0, a ^ 0 is a, and the order doesn't matter
Console.WriteLine($"{5 ^ 5} {5 ^ 0} {5 ^ 3 ^ 5} {3 ^ 5 ^ 5}");
int x = 0;
foreach (int v in new[] { 4, 1, 2, 1, 2 }) {
x ^= v;
Console.WriteLine($"after {v}: {x} ({Convert.ToString(x, 2).PadLeft(3, '0')})");
}
}
}
// 0 5 3 3
// after 4: 4 (100)
// after 1: 5 (101)
// after 2: 7 (111)
// after 1: 6 (110)
// after 2: 4 (100)package main
import "fmt"
func main() {
fmt.Println(5^5, 5^0, 5^3^5, 3^5^5) // a ^ a is 0, a ^ 0 is a, and the order doesn't matter
x := 0
for _, v := range []int{4, 1, 2, 1, 2} {
x ^= v
fmt.Printf("after %d: %d (%03b)\n", v, x, x)
}
}
// 0 5 3 3
// after 4: 4 (100)
// after 1: 5 (101)
// after 2: 7 (111)
// after 1: 6 (110)
// after 2: 4 (100)5 ^ 3 ^ 5 and 3 ^ 5 ^ 5 both gave 3: the two 5s cancel wherever they stand. The running value wanders, 4, 5, 7, 6, but once both 1s and both 2s are in, only the 4 is left.
Single Number
So Single Number is one loop, on the problem's three examples:
def single_number(nums): # every value twice but one: the pairs cancel
x = 0
for v in nums:
x ^= v
return x
print(single_number([2, 2, 1]), single_number([4, 1, 2, 1, 2]), single_number([1]))
# 1 4 1public class Main {
static int singleNumber(int[] nums) { // every value twice but one: the pairs cancel
int x = 0;
for (int v : nums) x ^= v;
return x;
}
public static void main(String[] args) {
System.out.println(singleNumber(new int[] {2, 2, 1}) + " " + singleNumber(new int[] {4, 1, 2, 1, 2}) + " "
+ singleNumber(new int[] {1}));
}
}
// 1 4 1#include <bits/stdc++.h>
using namespace std;
int singleNumber(const vector<int>& nums) { // every value twice but one: the pairs cancel
int x = 0;
for (int v : nums) x ^= v;
return x;
}
int main() {
cout << singleNumber({2, 2, 1}) << " " << singleNumber({4, 1, 2, 1, 2}) << " " << singleNumber({1}) << "\n";
}
// 1 4 1function singleNumber(nums) { // every value twice but one: the pairs cancel
let x = 0;
for (const v of nums) x ^= v;
return x;
}
console.log(singleNumber([2, 2, 1]), singleNumber([4, 1, 2, 1, 2]), singleNumber([1]));
// 1 4 1function singleNumber(nums: number[]): number { // every value twice but one: the pairs cancel
let x = 0;
for (const v of nums) x ^= v;
return x;
}
console.log(singleNumber([2, 2, 1]), singleNumber([4, 1, 2, 1, 2]), singleNumber([1]));
// 1 4 1using System;
class Program {
static int SingleNumber(int[] nums) { // every value twice but one: the pairs cancel
int x = 0;
foreach (int v in nums) x ^= v;
return x;
}
static void Main() {
Console.WriteLine($"{SingleNumber(new[] { 2, 2, 1 })} {SingleNumber(new[] { 4, 1, 2, 1, 2 })} {SingleNumber(new[] { 1 })}");
}
}
// 1 4 1package main
import "fmt"
func singleNumber(nums []int) int { // every value twice but one: the pairs cancel
x := 0
for _, v := range nums {
x ^= v
}
return x
}
func main() {
fmt.Println(singleNumber([]int{2, 2, 1}), singleNumber([]int{4, 1, 2, 1, 2}), singleNumber([]int{1}))
}
// 1 4 1O(n) time and O(1) extra space, which is what the problem asks for. The same idea finds the missing value in Missing Number: XOR every index from 0 to n with every value, and everything present cancels (Introduction to Arrays). And running XORs answer "XOR of a range" the way running sums answer range sums, because XOR undoes itself (Introduction to Prefix Sums).
Running XOR. Numbers arrive one at a time. Set the accumulator's bits to what it holds after each one, then check. Pairs cancel as they arrive; the value left at the end is the one without a pair.
Swapping without a temporary
XOR-Based Number swap asks to swap two variables with no third one. Three XORs do it: after a ^= b, a holds a ^ b; b ^= a gives b ^ a ^ b, the old a; and a ^= b gives a ^ b ^ a, the old b. Here it is on 5 and 9, then inside a loop that reverses an array by swapping each slot with its mirror and runs one step too far, to the middle slot included:
a, b = 5, 9
a ^= b # a holds a ^ b
b ^= a # b ^ (a ^ b) is the old a
a ^= b # (a ^ b) ^ the old a is the old b
print(a, b)
for name in ("xor swap", "temp swap"): # reverse, swapping i with n - 1 - i up to the middle, the middle too
arr = [1, 2, 3, 4, 5]
n = len(arr)
for i in range(n // 2 + 1):
j = n - 1 - i
if name == "xor swap":
arr[i] ^= arr[j]
arr[j] ^= arr[i]
arr[i] ^= arr[j]
else:
arr[i], arr[j] = arr[j], arr[i]
print(f"{name}:", *arr)
# 9 5
# xor swap: 5 4 0 2 1
# temp swap: 5 4 3 2 1public class Main {
public static void main(String[] args) {
int a = 5, b = 9;
a ^= b; // a holds a ^ b
b ^= a; // b ^ (a ^ b) is the old a
a ^= b; // (a ^ b) ^ the old a is the old b
System.out.println(a + " " + b);
for (String name : new String[] {"xor swap", "temp swap"}) { // reverse, up to the middle, the middle too
int[] arr = {1, 2, 3, 4, 5};
int n = arr.length;
for (int i = 0; i <= n / 2; i++) {
int j = n - 1 - i;
if (name.equals("xor swap")) {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
} else {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
StringBuilder line = new StringBuilder(name + ":");
for (int v : arr) line.append(" ").append(v);
System.out.println(line);
}
}
}
// 9 5
// xor swap: 5 4 0 2 1
// temp swap: 5 4 3 2 1#include <bits/stdc++.h>
using namespace std;
int main() {
int a = 5, b = 9;
a ^= b; // a holds a ^ b
b ^= a; // b ^ (a ^ b) is the old a
a ^= b; // (a ^ b) ^ the old a is the old b
cout << a << " " << b << "\n";
for (string name : {"xor swap", "temp swap"}) { // reverse, up to the middle, the middle too
vector<int> arr = {1, 2, 3, 4, 5};
int n = arr.size();
for (int i = 0; i <= n / 2; i++) {
int j = n - 1 - i;
if (name == "xor swap") {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
} else {
swap(arr[i], arr[j]);
}
}
cout << name << ":";
for (int v : arr) cout << " " << v;
cout << "\n";
}
}
// 9 5
// xor swap: 5 4 0 2 1
// temp swap: 5 4 3 2 1let a = 5, b = 9;
a ^= b; // a holds a ^ b
b ^= a; // b ^ (a ^ b) is the old a
a ^= b; // (a ^ b) ^ the old a is the old b
console.log(a, b);
for (const name of ["xor swap", "temp swap"]) { // reverse, up to the middle, the middle too
const arr = [1, 2, 3, 4, 5];
const n = arr.length;
for (let i = 0; i <= Math.floor(n / 2); i++) {
const j = n - 1 - i;
if (name === "xor swap") {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
} else {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
console.log(`${name}:`, ...arr);
}
// 9 5
// xor swap: 5 4 0 2 1
// temp swap: 5 4 3 2 1let a: number = 5, b: number = 9;
a ^= b; // a holds a ^ b
b ^= a; // b ^ (a ^ b) is the old a
a ^= b; // (a ^ b) ^ the old a is the old b
console.log(a, b);
for (const name of ["xor swap", "temp swap"]) { // reverse, up to the middle, the middle too
const arr: number[] = [1, 2, 3, 4, 5];
const n = arr.length;
for (let i = 0; i <= Math.floor(n / 2); i++) {
const j = n - 1 - i;
if (name === "xor swap") {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
} else {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
console.log(`${name}:`, ...arr);
}
// 9 5
// xor swap: 5 4 0 2 1
// temp swap: 5 4 3 2 1using System;
class Program {
static void Main() {
int a = 5, b = 9;
a ^= b; // a holds a ^ b
b ^= a; // b ^ (a ^ b) is the old a
a ^= b; // (a ^ b) ^ the old a is the old b
Console.WriteLine($"{a} {b}");
foreach (string name in new[] { "xor swap", "temp swap" }) { // reverse, up to the middle, the middle too
int[] arr = { 1, 2, 3, 4, 5 };
int n = arr.Length;
for (int i = 0; i <= n / 2; i++) {
int j = n - 1 - i;
if (name == "xor swap") {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
} else {
(arr[i], arr[j]) = (arr[j], arr[i]);
}
}
Console.WriteLine($"{name}: {string.Join(" ", arr)}");
}
}
}
// 9 5
// xor swap: 5 4 0 2 1
// temp swap: 5 4 3 2 1package main
import "fmt"
func main() {
a, b := 5, 9
a ^= b // a holds a ^ b
b ^= a // b ^ (a ^ b) is the old a
a ^= b // (a ^ b) ^ the old a is the old b
fmt.Println(a, b)
for _, name := range []string{"xor swap", "temp swap"} { // reverse, up to the middle, the middle too
arr := []int{1, 2, 3, 4, 5}
n := len(arr)
for i := 0; i <= n/2; i++ {
j := n - 1 - i
if name == "xor swap" {
arr[i] ^= arr[j]
arr[j] ^= arr[i]
arr[i] ^= arr[j]
} else {
arr[i], arr[j] = arr[j], arr[i]
}
}
fmt.Print(name, ":")
for _, v := range arr {
fmt.Print(" ", v)
}
fmt.Println()
}
}
// 9 5
// xor swap: 5 4 0 2 1
// temp swap: 5 4 3 2 1With the XOR swap the middle 3 became 0 in all seven. At the middle, i and j are the same slot, and the first XOR sets it to a ^ a, which is 0: there's no second copy left to recover it from. The swap with a temporary just swapped the slot with itself. Interviews ask for the XOR swap to see that you know XOR; in real code, write the temporary.
Two values without a pair
Two odd Occuring Numbers in an Array (LeetCode's Single Number III) has two values that appear once and everything else twice. XORing everything leaves x ^ y, which isn't 0, since x and y differ. Any 1 in it is a bit where x and y differ, and x & −x picks the lowest one (Introduction to Bit Manipulation). Split all the values by that bit: x and y land in different groups, and each pair lands whole in one group, where it cancels:
def two_singles(nums): # two values once, the rest twice
both = 0
for v in nums:
both ^= v # the pairs cancel: x ^ y is left
low = both & -both # its lowest set bit: x and y differ there
x = y = 0
for v in nums:
if v & low:
x ^= v # the values with that bit: x, and whole pairs
else:
y ^= v # the rest: y, and the other pairs
return sorted((x, y))
print(*two_singles([1, 2, 1, 3, 2, 5]))
print(*two_singles([-1, 0]))
print(*two_singles([0, 1]))
# 3 5
# -1 0
# 0 1public class Main {
static int[] twoSingles(int[] nums) { // two values once, the rest twice
int both = 0;
for (int v : nums) both ^= v; // the pairs cancel: x ^ y is left
int low = both & -both; // its lowest set bit: x and y differ there
int x = 0, y = 0;
for (int v : nums) {
if ((v & low) != 0) x ^= v; // the values with that bit: x, and whole pairs
else y ^= v; // the rest: y, and the other pairs
}
return new int[] {Math.min(x, y), Math.max(x, y)};
}
public static void main(String[] args) {
for (int[] nums : new int[][] {{1, 2, 1, 3, 2, 5}, {-1, 0}, {0, 1}}) {
int[] r = twoSingles(nums);
System.out.println(r[0] + " " + r[1]);
}
}
}
// 3 5
// -1 0
// 0 1#include <bits/stdc++.h>
using namespace std;
pair<int, int> twoSingles(const vector<int>& nums) { // two values once, the rest twice
unsigned both = 0; // unsigned, so -both can't overflow
for (int v : nums) both ^= v; // the pairs cancel: x ^ y is left
unsigned low = both & -both; // its lowest set bit: x and y differ there
int x = 0, y = 0;
for (int v : nums) {
if (v & low) x ^= v; // the values with that bit: x, and whole pairs
else y ^= v; // the rest: y, and the other pairs
}
return {min(x, y), max(x, y)};
}
int main() {
for (vector<int> nums : {vector<int>{1, 2, 1, 3, 2, 5}, {-1, 0}, {0, 1}}) {
auto [x, y] = twoSingles(nums);
cout << x << " " << y << "\n";
}
}
// 3 5
// -1 0
// 0 1function twoSingles(nums) { // two values once, the rest twice
let both = 0;
for (const v of nums) both ^= v; // the pairs cancel: x ^ y is left
const low = both & -both; // its lowest set bit: x and y differ there
let x = 0, y = 0;
for (const v of nums) {
if (v & low) x ^= v; // the values with that bit: x, and whole pairs
else y ^= v; // the rest: y, and the other pairs
}
return [Math.min(x, y), Math.max(x, y)];
}
for (const nums of [[1, 2, 1, 3, 2, 5], [-1, 0], [0, 1]]) console.log(...twoSingles(nums));
// 3 5
// -1 0
// 0 1function twoSingles(nums: number[]): [number, number] { // two values once, the rest twice
let both = 0;
for (const v of nums) both ^= v; // the pairs cancel: x ^ y is left
const low = both & -both; // its lowest set bit: x and y differ there
let x = 0, y = 0;
for (const v of nums) {
if (v & low) x ^= v; // the values with that bit: x, and whole pairs
else y ^= v; // the rest: y, and the other pairs
}
return [Math.min(x, y), Math.max(x, y)];
}
for (const nums of [[1, 2, 1, 3, 2, 5], [-1, 0], [0, 1]]) console.log(...twoSingles(nums));
// 3 5
// -1 0
// 0 1using System;
class Program {
static (int, int) TwoSingles(int[] nums) { // two values once, the rest twice
int both = 0;
foreach (int v in nums) both ^= v; // the pairs cancel: x ^ y is left
int low = both & -both; // its lowest set bit: x and y differ there
int x = 0, y = 0;
foreach (int v in nums) {
if ((v & low) != 0) x ^= v; // the values with that bit: x, and whole pairs
else y ^= v; // the rest: y, and the other pairs
}
return (Math.Min(x, y), Math.Max(x, y));
}
static void Main() {
foreach (int[] nums in new[] { new[] { 1, 2, 1, 3, 2, 5 }, new[] { -1, 0 }, new[] { 0, 1 } }) {
var (x, y) = TwoSingles(nums);
Console.WriteLine($"{x} {y}");
}
}
}
// 3 5
// -1 0
// 0 1package main
import "fmt"
func twoSingles(nums []int) (int, int) { // two values once, the rest twice
both := 0
for _, v := range nums {
both ^= v // the pairs cancel: x ^ y is left
}
low := both & -both // its lowest set bit: x and y differ there
x, y := 0, 0
for _, v := range nums {
if v&low != 0 {
x ^= v // the values with that bit: x, and whole pairs
} else {
y ^= v // the rest: y, and the other pairs
}
}
return min(x, y), max(x, y)
}
func main() {
for _, nums := range [][]int{{1, 2, 1, 3, 2, 5}, {-1, 0}, {0, 1}} {
fmt.Println(twoSingles(nums))
}
}
// 3 5
// -1 0
// 0 1
On [1, 2, 1, 3, 2, 5], the XOR of all six is 6, 110, and its lowest set bit is 2. 2, 3 and 2 have that bit, and XOR to 3; 1, 1 and 5 don't, and XOR to 5. The C++ version keeps the XOR in an unsigned: when it's −2³¹, negating a 32-bit int overflows, which C++ leaves undefined. Java, C#, JavaScript and TypeScript wrap around, and Python and Go have the room.
Adding without +
Sum of Two Integers forbids + and −. Adding in binary is XOR plus carries: a ^ b is the sum with every carry dropped, and a & b marks the columns that carry, so (a & b) << 1 is the carries, moved one place left to where they land. Add those two the same way, until there's nothing left to carry:
MASK = 0xFFFFFFFF # Python's ints have no width: keep 32 bits, as an int does elsewhere
def get_sum(a, b): # XOR adds without carrying; AND, shifted left, is the carry
a, b = a & MASK, b & MASK
while b != 0:
a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK
return a - (1 << 32) if a >> 31 else a # bit 31 set: read it as negative
for a, b in ((1, 2), (2, 3), (13, 7), (-1, 1), (-12, -8)):
print(f"{a} + {b} = {get_sum(a, b)}")
# 1 + 2 = 3
# 2 + 3 = 5
# 13 + 7 = 20
# -1 + 1 = 0
# -12 + -8 = -20public class Main {
static int getSum(int a, int b) { // XOR adds without carrying; AND, shifted left, is the carry
while (b != 0) {
int carry = (a & b) << 1;
a ^= b;
b = carry;
}
return a;
}
public static void main(String[] args) {
int[][] pairs = {{1, 2}, {2, 3}, {13, 7}, {-1, 1}, {-12, -8}};
for (int[] p : pairs) System.out.println(p[0] + " + " + p[1] + " = " + getSum(p[0], p[1]));
}
}
// 1 + 2 = 3
// 2 + 3 = 5
// 13 + 7 = 20
// -1 + 1 = 0
// -12 + -8 = -20#include <bits/stdc++.h>
using namespace std;
int getSum(int a, int b) { // XOR adds without carrying; AND, shifted left, is the carry
while (b != 0) {
int carry = (a & b) << 1;
a ^= b;
b = carry;
}
return a;
}
int main() {
int pairs[][2] = {{1, 2}, {2, 3}, {13, 7}, {-1, 1}, {-12, -8}};
for (auto& p : pairs) cout << p[0] << " + " << p[1] << " = " << getSum(p[0], p[1]) << "\n";
}
// 1 + 2 = 3
// 2 + 3 = 5
// 13 + 7 = 20
// -1 + 1 = 0
// -12 + -8 = -20function getSum(a, b) { // XOR adds without carrying; AND, shifted left, is the carry
while (b !== 0) {
const carry = (a & b) << 1;
a ^= b;
b = carry;
}
return a;
}
for (const [a, b] of [[1, 2], [2, 3], [13, 7], [-1, 1], [-12, -8]]) console.log(`${a} + ${b} = ${getSum(a, b)}`);
// 1 + 2 = 3
// 2 + 3 = 5
// 13 + 7 = 20
// -1 + 1 = 0
// -12 + -8 = -20function getSum(a: number, b: number): number { // XOR adds without carrying; AND, shifted left, is the carry
while (b !== 0) {
const carry = (a & b) << 1;
a ^= b;
b = carry;
}
return a;
}
for (const [a, b] of [[1, 2], [2, 3], [13, 7], [-1, 1], [-12, -8]]) console.log(`${a} + ${b} = ${getSum(a, b)}`);
// 1 + 2 = 3
// 2 + 3 = 5
// 13 + 7 = 20
// -1 + 1 = 0
// -12 + -8 = -20using System;
class Program {
static int GetSum(int a, int b) { // XOR adds without carrying; AND, shifted left, is the carry
while (b != 0) {
int carry = (a & b) << 1;
a ^= b;
b = carry;
}
return a;
}
static void Main() {
int[][] pairs = { new[] { 1, 2 }, new[] { 2, 3 }, new[] { 13, 7 }, new[] { -1, 1 }, new[] { -12, -8 } };
foreach (int[] p in pairs) Console.WriteLine($"{p[0]} + {p[1]} = {GetSum(p[0], p[1])}");
}
}
// 1 + 2 = 3
// 2 + 3 = 5
// 13 + 7 = 20
// -1 + 1 = 0
// -12 + -8 = -20package main
import "fmt"
func getSum(a, b int) int { // XOR adds without carrying; AND, shifted left, is the carry
for b != 0 {
carry := (a & b) << 1
a ^= b
b = carry
}
return a
}
func main() {
for _, p := range [][2]int{{1, 2}, {2, 3}, {13, 7}, {-1, 1}, {-12, -8}} {
fmt.Printf("%d + %d = %d\n", p[0], p[1], getSum(p[0], p[1]))
}
}
// 1 + 2 = 3
// 2 + 3 = 5
// 13 + 7 = 20
// -1 + 1 = 0
// -12 + -8 = -20
13 + 7 took three rounds. Negative numbers work because a carry that reaches the top bit, bit 31 of an int or bit 63 of Go's, is shifted out and gone, so the loop ends: −1 + 1 printed 0. Python's integers have no top bit to fall off, which is why its version masks every step to 32 bits and reads a set bit 31 as negative. Without the mask:
def get_sum(a, b): # the loop the other six languages run, on Python's unbounded ints
while b != 0:
a, b = a ^ b, (a & b) << 1
return a
print(get_sum(13, 7), flush=True)
print(get_sum(-1, 1), flush=True)
# 20
# (no second line: still looping when the judge stopped it after 2 s)13 + 7 came out 20, and then −1 + 1 never finished: the judge stopped it after 2 seconds. −1 has 1s forever to the left in Python, so the carry kept moving left forever.
When values come three times
XOR cancels pairs, not triples: a ^ a ^ a is a. When every value appears three times except one, as in LeetCode's Single Number II, count the 1s in each of the 32 bit positions. The triples add a multiple of 3 to every count, so a count that isn't a multiple of 3 is a bit of the single value:
def single_of_three(nums): # every value three times but one: count the 1s in each bit, mod 3
result = 0
for k in range(32):
ones = sum((v >> k) & 1 for v in nums)
if ones % 3 != 0:
result |= 1 << k # the single value has this bit
return result - (1 << 32) if result >> 31 else result # bit 31 set: read it as negative
print(single_of_three([2, 2, 3, 2]), single_of_three([0, 1, 0, 1, 0, 1, 99]),
single_of_three([-2, -2, 1, 1, 4, 1, 4, 4, -4, -2]))
# 3 99 -4public class Main {
static int singleOfThree(int[] nums) { // every value three times but one: count each bit's 1s, mod 3
int result = 0;
for (int k = 0; k < 32; k++) {
int ones = 0;
for (int v : nums) ones += (v >> k) & 1;
if (ones % 3 != 0) result |= 1 << k; // the single value has this bit
}
return result;
}
public static void main(String[] args) {
System.out.println(singleOfThree(new int[] {2, 2, 3, 2}) + " " + singleOfThree(new int[] {0, 1, 0, 1, 0, 1, 99})
+ " " + singleOfThree(new int[] {-2, -2, 1, 1, 4, 1, 4, 4, -4, -2}));
}
}
// 3 99 -4#include <bits/stdc++.h>
using namespace std;
int singleOfThree(const vector<int>& nums) { // every value three times but one: count each bit's 1s, mod 3
int result = 0;
for (int k = 0; k < 32; k++) {
int ones = 0;
for (int v : nums) ones += (v >> k) & 1;
if (ones % 3 != 0) result |= 1 << k; // the single value has this bit
}
return result;
}
int main() {
cout << singleOfThree({2, 2, 3, 2}) << " " << singleOfThree({0, 1, 0, 1, 0, 1, 99}) << " "
<< singleOfThree({-2, -2, 1, 1, 4, 1, 4, 4, -4, -2}) << "\n";
}
// 3 99 -4function singleOfThree(nums) { // every value three times but one: count each bit's 1s, mod 3
let result = 0;
for (let k = 0; k < 32; k++) {
let ones = 0;
for (const v of nums) ones += (v >> k) & 1;
if (ones % 3 !== 0) result |= 1 << k; // the single value has this bit
}
return result;
}
console.log(singleOfThree([2, 2, 3, 2]), singleOfThree([0, 1, 0, 1, 0, 1, 99]),
singleOfThree([-2, -2, 1, 1, 4, 1, 4, 4, -4, -2]));
// 3 99 -4function singleOfThree(nums: number[]): number { // every value three times but one: count each bit's 1s, mod 3
let result = 0;
for (let k = 0; k < 32; k++) {
let ones = 0;
for (const v of nums) ones += (v >> k) & 1;
if (ones % 3 !== 0) result |= 1 << k; // the single value has this bit
}
return result;
}
console.log(singleOfThree([2, 2, 3, 2]), singleOfThree([0, 1, 0, 1, 0, 1, 99]),
singleOfThree([-2, -2, 1, 1, 4, 1, 4, 4, -4, -2]));
// 3 99 -4using System;
class Program {
static int SingleOfThree(int[] nums) { // every value three times but one: count each bit's 1s, mod 3
int result = 0;
for (int k = 0; k < 32; k++) {
int ones = 0;
foreach (int v in nums) ones += (v >> k) & 1;
if (ones % 3 != 0) result |= 1 << k; // the single value has this bit
}
return result;
}
static void Main() {
Console.WriteLine($"{SingleOfThree(new[] { 2, 2, 3, 2 })} {SingleOfThree(new[] { 0, 1, 0, 1, 0, 1, 99 })} "
+ $"{SingleOfThree(new[] { -2, -2, 1, 1, 4, 1, 4, 4, -4, -2 })}");
}
}
// 3 99 -4package main
import "fmt"
func singleOfThree(nums []int32) int32 { // every value three times but one: count each bit's 1s, mod 3
var result int32
for k := 0; k < 32; k++ {
ones := 0
for _, v := range nums {
ones += int((v >> k) & 1)
}
if ones%3 != 0 {
result |= 1 << k // the single value has this bit
}
}
return result
}
func main() {
fmt.Println(singleOfThree([]int32{2, 2, 3, 2}), singleOfThree([]int32{0, 1, 0, 1, 0, 1, 99}),
singleOfThree([]int32{-2, -2, 1, 1, 4, 1, 4, 4, -4, -2}))
}
// 3 99 -43, 99 and −4: the third list's −4 has bit 31 set, which the 32-bit languages read as negative by themselves; Python, again, needs the last line. 32 passes over the array is O(32 n), still linear, with O(1) extra space.
Spotting it
The clues: "appears twice" with one or two exceptions, "constant extra space" on what looks like a counting problem, "swap without a temporary", "without + or −", pairs of equal values that should cancel, or a range's XOR. Near misses:
- Counting how many times each value appears, with no pairing: a hash map (Frequency Counting with Hash Maps).
- The largest XOR of two numbers in an array: a trie of their bits, highest first (Tries).
- How many subarrays XOR to k: running XORs in a hash map (Prefix Sums with a Hash Map).
Mistakes that cost an interview
^ as a power. In all seven languages ^ is XOR, so 2 ^ 3 isn't 8:
print(2 ^ 3, 2 ** 3) # XOR, then the power
# 1 8public class Main {
public static void main(String[] args) {
System.out.println((2 ^ 3) + " " + (int) Math.pow(2, 3)); // XOR, then the power
}
}
// 1 8#include <bits/stdc++.h>
using namespace std;
int main() {
cout << (2 ^ 3) << " " << (int) pow(2, 3) << "\n"; // XOR, then the power
}
// 1 8console.log(2 ^ 3, 2 ** 3); // XOR, then the power
// 1 8console.log(2 ^ 3, 2 ** 3); // XOR, then the power
// 1 8using System;
class Program {
static void Main() {
Console.WriteLine($"{2 ^ 3} {(int)Math.Pow(2, 3)}"); // XOR, then the power
}
}
// 1 8package main
import (
"fmt"
"math"
)
func main() {
fmt.Println(2^3, int(math.Pow(2, 3))) // XOR, then the power
}
// 1 8It printed 1, which is 10 ^ 11 in binary. The power is ** in Python, JavaScript and TypeScript, and a function in the others.
Swapping a slot with itself. The XOR swap zeroes it, as the reverse above showed. Guard with if (i != j), or use a temporary.
Sum of Two Integers in Python without a mask. With a negative number in the sum, the carry can chase its endless 1s for ever: −1 + 1 never finished above.
Starting the XOR at something other than 0. 0 is the value that changes nothing, as 0 is for a sum; starting from the first element and then XORing every element counts it twice and cancels it.
Check yourself
Quiz
1 / 6Multiple choice
What is 6 ^ 9 ^ 6?
Multiple choice
A running XOR starts at 0 and takes 4, 1, 2 and 1. What does it hold now?
Multiple choice
The XOR of the two unpaired values is 6. Which bit does
both & -both pick to split them?Multiple choice
a ^= b; b ^= a; a ^= b; runs with a and b naming the same variable. What's left in it?Multiple choice
Sum of Two Integers on 12 + 5: after the first round, what are a ^ b and the carry?
Multiple choice
What does
2 ^ 3 print in Java?Practice
In this section, easy to hard:
- XOR-Based Number swap: three XORs, and keep the two names apart.
- Single Number: one running XOR.
- Two odd Occuring Numbers in an Array: XOR all, split by the lowest set bit, XOR each group.
- Sum of Two Integers: XOR for the sum, AND shifted left for the carry, until no carry; mask to 32 bits in Python.
Next: Bitmasks and Bitwise Arithmetic, where a number's bits stand for a set.