Questions tagged [xor]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
20 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$$
0
votes
1answer
19 views

What happens when the xor inBlock chaining returns false?

"With block cipher, each plaintext block is XOR-ed with the previous ciphertext block and then encrypted, this is known as block chaining. This prevents identical blocks of plaintext from producing ...
1
vote
2answers
45 views

If XOR of n distinct numbers is ANDed over one of the number, the result would be zero

Say we Have n distinct numbers x1,x2,....xn And we xor the result xoredResult = x1^x2...^xn And if we AND(&) with one ...
3
votes
2answers
397 views

Minimum XOR for queries

I was asked the following question in an interview. Given an array $A$ with $n$ integers and an array $B$ with $m$ integers. For each integer $b \in B$ return and integer $a \in A$ such that $a \...
2
votes
1answer
70 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 ...
3
votes
1answer
111 views

Is is possible to determine if a given number is xor combination of some numbers?

I have been given a number Y which is ($a$ xor $b$ xor $c$ xor $d$ xor $e$ ) of some numbers ($a$,$b$,$c$,$d$,$e$) and another no X. Now i have to determine if X is a xor combination of ($a$,$b$,$c$,$...
1
vote
0answers
33 views

Take k numbers from the array and xor them with x to get maximum sum [duplicate]

Given an array A of n numbers and integers k and x. We can perform the following operation any number of times (including zero times). Take exactly k numbers from the array and replace each of them ...
2
votes
1answer
201 views

Can I simplify successive XOR operations?

I'm doing an online programming challenge where successive XOR operations are used (from codewars.com, if you don't want to create an account, here are the instructions). We have a rectangle of known ...
2
votes
0answers
58 views

Implementing depth-3 circuit for XOR

In this set of notes, they claim that there is a size $O(2^{\sqrt n})$ depth-3 circuit (OR -AND -OR) that implements XOR. I tried for a little bit to figure out how to do this, but couldn't find ...
0
votes
1answer
43 views

Find value of $a$ or $b$ of two XOR equations

Is it possible to find $a$ or $b$ given that $a \oplus b = c$ and $c \oplus b = a$ when I only have the value of $b$?
1
vote
1answer
143 views

Representing chained XOR operations as linear inequalities

I'm trying to solve an integer linear program (ILP) in which a constraint of the following kind must be met: $x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$ where $\oplus$ is the binary xor operator. ...
1
vote
1answer
178 views

Is the bitwise-xor of a Uniform bit string and a non_uniform bit string Uniform?

Having two bit strings $x,y \in \left\{0,1\right\}^n$, where $x$ is selected following a uniform distribution but $y$ is not. Is $z = x \oplus y$ uniform?
2
votes
1answer
136 views

Using Yao's principle to find a lower bound

This is a HW question, so I'm not expecting any answers, just a general guidance/help. Definition. Given $\underset{\neq0}{\underbrace{s}}\in\left\{ 0,1\right\} ^{n}$, a function $f:\left\{ 0,1\right\...
-1
votes
1answer
161 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 ...
3
votes
1answer
62 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 ...
3
votes
2answers
161 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$ ...
3
votes
1answer
339 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)$...
2
votes
1answer
336 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 ...
5
votes
1answer
960 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. ...
2
votes
1answer
43 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 ...
2
votes
2answers
87 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 ...
4
votes
5answers
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?
1
vote
2answers
1k 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 ...
0
votes
1answer
1k 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 ...
7
votes
1answer
294 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,\...
11
votes
3answers
2k 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: ...
0
votes
1answer
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 ...
2
votes
2answers
244 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 ...
0
votes
1answer
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. ...
9
votes
1answer
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 ...
4
votes
2answers
658 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 $(...
2
votes
1answer
1k views

One time pad, get plaintext using ciphers encoded with the same key

I'm trying to solve a problem: I have 11 ciphers encoded with the same key. My aim is to decode target cipher. If I do xor C1, C2 (ciphers encoded with the same key) I do get M1 xor M2 (where M1, M2 ...
8
votes
2answers
930 views

How can I find minimum number required to add to sequence such that their xor becomes zero

Given a sequence of natural numbers, you can add any natural number to any number in the sequence such that their xor becomes zero. My goal is to minimize the sum of added numbers. Consider the ...