# 0.3: Strings

- Page ID
- 7448

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.

*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\).

*We write \(x \| y\) to denote the result of concatenating \(x\) and \(y\).*