Skip to main content

# 0.3: Strings


We write $$\{0,1\}^{n}$$ to denote the set of $$n$$-bit binary strings, and $$\{0,1\}^{*}$$ to denote the set of all (finite-length) binary strings. When $$x$$ is a string of bits, we write $$|x|$$ to denote the length (in bits) of that string, and we write $$\bar{x}$$ to denote the result of flipping every bit in $$x$$. When it’s clear from context that we’re talking about strings instead of numbers, we write $$0^{n}$$ and $$1^{n}$$ to denote strings of $$n$$ zeroes and $$n$$ ones, respectively (rather than the result of raising the integers 0 or 1 to the $$n$$ power). As you might have noticed, I also try to use a different font and color for characters (including bits, anything that could be used to build a string through concatenation) vs. integers.

##### Definition $$0.5 \, \left ( \oplus, \, \tiny{\textrm{XOR}} \right )$$

When $$x$$ and $$y$$ are strings of the same length, we write $$x \oplus y$$ to denote the bitwise exclusive-or $$\left ( \tiny{\textrm{XOR}}\right )$$ of the two strings. The expression $$x \oplus y$$ is generally not defined when the strings are different lengths, but in rare occasions it is useful to consider the shorter string being padded with $$0 s$$. When that’s the case, we must have an explicit convention about whether the shorter string is padded with leading $$0 s$$ or trailing $$0 s$$.

For example, $$0011 \oplus 0101=0110$$. The following facts about the $$\tiny{\textrm{XOR}}$$ operation are frequently useful: \begin{aligned} x \oplus x &=000 \cdots & & \text { $$\tiny{\textrm{XOR}}$$'ing a string with itself results in zeroes. } \\ x \oplus 000 \cdots &=x & & \text { $$\tiny{\textrm{XOR}}$$'ing with zeroes has no effect. } \\ x \oplus 111 \cdots &=\bar{x} & & \text { $$\tiny{\textrm{XOR}}$$'ing with ones flips every bit. } \\ x \oplus y &=y \oplus x & & \text { $$\tiny{\textrm{XOR}}$$ is symmetric. } \\ (x \oplus y) \oplus z &=x \oplus(y \oplus z) & & \text { $$\tiny{\textrm{XOR}}$$ is associative. } \end{aligned} See if you can use these properties to derive the very useful fact below: $a=b \oplus c \Longleftrightarrow b=a \oplus c \Longleftrightarrow c=a \oplus b .\notag$ There are a few ways to think about $$\tiny{\textrm{XOR}}$$ that may help you in this class:

Bit-flipping: Note that $$\tiny{\textrm{XOR}}$$’ing a bit with 0 has no effect, while $$\tiny{\textrm{XOR}}$$’ing with 1 flips that bit. You can think of $$x \oplus y$$ as: "starting with $$x$$, flip the bits at all the positions where $$y$$ has a 1." So if $$y$$ is all I’s, then $$x \oplus y$$ gives the bitwise-complement of $$x$$. If $$y=1010 \cdots$$ then $$x \oplus y$$ means "(the result of) flipping every other bit in $$x$$."

Many concepts in this course can be understood in terms of bit-flipping. For example, we might ask "what happens when I flip the first bit of $$x$$ and send it into the algorithm?" This kind of question could also be phrased as "what happens when I send $$x \oplus 1000 \cdots$$ into the algorithm?" Usually there is nothing special about flipping just the first bit of a string, so it will often be quite reasonable to generalize the question as "what happens when I send $$x \oplus y$$ into the algorithm, for an arbitrary (not-all-zeroes) string $$y$$ ?"

Addition mod-2: $$\tiny{\textrm{XOR}}$$ is just addition mod 2 in every bit. This way of thinking about $$\tiny{\textrm{XOR}}$$ helps to explain why "algebraic" things like $$(x \oplus y) \oplus z=x \oplus(y \oplus z)$$ are true. They are true for addition, so they are true for $$\tiny{\textrm{XOR}}$$.

This also might help you remember why $$x \oplus x$$ is all zeroes. If instead of $$\tiny{\textrm{XOR}}$$ we used addition, we would surely write $$x+x=2 x$$. Since $$2 \equiv_{2} 0$$, we get that $$2 x$$ is congruent to $$0 x=0$$.

##### Definition $$0.6$$ $$(\|$$, concatenation)

We write $$x \| y$$ to denote the result of concatenating $$x$$ and $$y$$.

This page titled 0.3: Strings is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) .

• Was this article helpful?