Questions tagged [xor]
The xor tag has no summary.
47 questions
1
vote
1
answer
73
views
Can A xor (B and C) be transformed into SAT-XNF?
I'm trying to wrangle a problem into XOR-SAT, but I'm stuck with a couple of terms in the form of :
A xor (B and C)
Does any one knows if it is possible (or impossible for that matter) to turn them ...
- 113
0
votes
1
answer
135
views
Improve performances of Gauss-Jordan (XOR-SAT) Algorithm?
In this question I was looking for an algorithm to solve what seems to be a XOR-SAT problem.
Let's consider this equation system :
...
- 295
1
vote
1
answer
283
views
Prove that Gaussian elimination solves maximum XOR subset problem?
Given an array of positive integers. Find the subset that maximizes the XOR of all of its elements? This can be solved by "Gaussian elimination" in the following manner:
Pick the largest ...
0
votes
1
answer
179
views
Prove that it is impossible to construct the toffoli gate using only CNOT gates
Show that it is not possible to construct the toffoli gate using only CNOT gates, given we are allowed to choose any number of ancilla bits.
My Attempt
The action of a toffoli gate can be defined as,
...
- 139
1
vote
1
answer
204
views
Subset ${\tt XOR}$ problem
Motivation. This is a variant of the subset sum problem involving the bitwise ${\tt XOR}$ operation.
Problem. Given a set $X$ of $n$ bit-strings of length $n$, determine if there is a non-empty subset ...
1
vote
4
answers
365
views
XOR pair frequency queries
We are given an array of length $N$ and $Q$ queries (offline) where each query is a value $K$, for each query we need to count number of pairs in array with XOR $K$.
If $N$ and $Q$ can both be upto $...
- 333
4
votes
3
answers
6k
views
Calculating XOR of all numbers from 1 to n: Why does this method work?
Given a number n, the task is to find the XOR of every number from 1 to n. Why does the following algorithm work?
Find the remainder of n by moduling it with 4.
If rem = 0, then XOR will be same as n....
- 89
0
votes
1
answer
168
views
What property of XOR makes this algorithm work?
I'm having trouble figuring out why using XOR for this problem works; I've done it a couple of times by-hand, and can't really seem to understand it. I know that XOR is commutative and associative, ...
-3
votes
1
answer
283
views
Bitwise X-OR properties for competitive programming
What are some equations/ inequalities and properties of bitwise X-OR that can be used in competitive programming.
0
votes
0
answers
240
views
Effecient encoding of sum equality in cnf+xor
I am wondering as to how to efficiently encode the following subcircuit for a binary satisfiability solver (cnf, and optionally xor clauses, if this helps):
...
- 1,500
3
votes
1
answer
293
views
Minimizing series of XORs
Suppose you receive a list of $n$ instructions on $k$ boolean variables where each instruction has the form
$$x_i \leftarrow x_i \oplus x_j,$$
(where $\oplus$ is the binary XOR) can we efficiently ...
- 14k
1
vote
1
answer
99
views
XOR of three integers where each pair's XOR is the other integer
I have three positive integers, a, b, and c. I know that $a\oplus b\oplus c=0$, so I got that each pairwise xor has to be the other positive integer. $a\oplus b=c$, $b\oplus c=a$, and so on, but I can'...
- 11
1
vote
1
answer
86
views
Where is the theory about "binary toggling games"?
Let us -- using parameters $M, N$ and $L$ --
create an ordered set of size $M$ of $N$-bit long vectors $V$ and initialize them randomly: $V_k[i] = b \sim Bin(n=1, p=0.5)\ \forall i \in
\{0\ ..\ N-1\}...
- 127
-2
votes
1
answer
299
views
Manually Performing ECB & CBC
I am learning about block ciphers and while I understand the concept of Electronic Codeblock mode and cipher block chaining, I could not find any relevant practical examples online. Can someone ...
- 167
0
votes
0
answers
83
views
Minimum pair-wise XOR of elements from two sets
I have two sets, $A$ and $B$, which both contain a large amount of hashed values.
What is the most efficient way of computing:
$$\min_{i,j} A_i \otimes B_j$$
- 103