# Questions tagged [xor]

The tag has no usage guidance.

28 questions
Filter by
Sorted by
Tagged with
92 views

125 views

### How many solutions are there for a XOR-SAT formula? [closed]

Does anyone know how many solutions there are for a XOR-SAT formula? And how do the variables in solutions distribute? For example, if (x0=1, x1=0, x2=1) is a solution for a XOR-SAT formula, how does ...
54 views

### Coin flipping problem on an $n \times m$ grid

There are $n \times m$ coins lying on an $n \times m$ grid. Each coin is either facing up or down initially. We can do the following operation repeatedly: Flipping a row of coins; Flipping a colomn ...
149 views

### NP-complete language as a result of xoring two PTIME languages

We define xor operation on languages $L,M\subseteq \{0,1\}^*$: $$L\oplus M = \{u\oplus v :|u|=|v|, u\in L, v\in M\}$$ $\oplus$ is defined as xor on postions, for example: $001\oplus 100=101$ ...
318 views

### Subset of numbers whose XOR has least Hamming weight

I'm given $n$ numbers (let's say of some 100 bits or so). Is there a way to find a non-empty subset xor of these $n$ numbers which has the least Hamming weight (no. of set bits) in better than $O(2^n)$...
303 views

### Minimum depth of addition and multiplication circuit using XOR and AND gates

What are the minimum depth circuits possible for addition and multiplication of two n-bit numbers using just AND and XOR gates? I read somewhere that we can achieve constant depth for addition if we ...
805 views

### Path in a graph with a given xor of weights of edges

I have an undirected weighted graph with $V$ vertices and $E$ edges. Weight of a path is a xor of weights of the edges on this path. Paths can pass through the same vertices and edges many times. ...
37 views

### Find number X by asking Hamming distance between X and Y in binary representation

We need to find unknown 16-bit integer X. We can ask "how many '1'-bits in number X xor Y" (Y is 16-bit too). What best strategy to find X? Or what minimum number of questions? For example, if answer ...
77 views

### Can I use “XORing” in my thesis?

I'm currently writing my bachelor thesis and explain some algorithms where the XOR-operation is used. Can I use "XORing" or "XORed" in my thesis or is this too informal? For example: "xoring the ...
2k views

### XOR two numbers

Is there an intuitive meaning of XOR of two numbers not involving binary and just decimal? Or is is always converted into binary and then XORed?
930 views

### XOR of one-way function

Considering the top answer to the question “If xor-ing a one way function with different input, is it still a one way function?”… The function is no longer one-way. we build a counter example ...
847 views

### Rewriting gates such as XOR into three basic gates? [closed]

How would I rewrite an XOR gate into the three basic logic gates (AND, OR, NOT). To be more specific, I have to write it in such a way with 2 NOT gates, 2 OR gates, and 1 AND gate. I also have to do ...
246 views

### Is weighted XOR-SAT NP-hard?

Given $n$ boolean variables $x_1,\ldots,x_n$ each of which is assigned a positive cost $c_1,\ldots,c_n\in\mathbb{Z}_{>0}$ and a boolean function $f$ on these variables given in the form f(x_1,\...
1k views

### Is 2-SAT with XOR-relations NP-complete?

I'm wondering if there is a polynomial algorithm for "2-SAT with XOR-relations". Both 2-SAT and XOR-SAT are in P, but is its combination? Example Input: 2-SAT part: ...
1k views

### Express XOR with multiple inputs in zero-one integer linear programming (ILP)

In the below post, it is explained how to express xor of two variables as linear inequalities. Express boolean logic operations in zero-one integer linear programming (ILP) Naturally, the xor of ...
237 views

### Is my simplified explaination of the XOR swap correct?

The XOR swap is a well-known in-place algorithm to swap two values, by XOR:ing them bitwise. It goes as follows: a = a ^ b b = a ^ b a = a ^ b Now, I was ...
1k views

### Odd Parity Function [closed]

I am trying to define a Odd Parity Function that takes three 1 bit inputs and will output a 1 if the 3 bits are odd as a Boolean function. ...
1k views

### How to construct this generalized xor without needing an extra vector?

Operator - Generalized Symmetric Difference If you take binary xor and generalize it to other radices you can do so by the absolute value of the difference of each element in a radix vector. However ...
615 views

### Minimizing the full adder - where did this XOR come from?

When minimizing the full adder, I don't understand why $A(\bar{B}\bar{C} + BC)$ reduces to $A\overline{(B\oplus{C})}.$ $(\bar{B}\bar{C} + BC)\to (B\oplus{C})$ is partially decipherable, but why is \$(...