Questions tagged [xor]

The tag has no usage guidance.

29 questions
Filter by
Sorted by
Tagged with
56 views

find maximum sum of xors

we are given an Array Array size <= 10^4 . 0 <= A[i] <= 15 We need to partition the array into 4 subsets (each subset can have zero or more elements ). Take xor of each subset and sum ...
96 views

126 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 ...
150 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$ ...
322 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)$...
305 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 ...
846 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 ...
79 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?
969 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 ...
871 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 ...
247 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 ...
620 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 \$(...