<< | < | home | > | >>


The first "medium" problem in Cracking the Coding Interview is this:

Challenge: Swap two numbers in place without using a temporary variable.

There are a number of ways to solve this problem, but the first that came to mind was XOR swap:

Why does this work? Here's how Wikipedia illustrates it:

My thought process when working through an explanation like this is something like the following:

Wikipedia's explanation requires me to load a bunch of ones and zeros into my head and step through the example like a machine. Existential crises follow:

Then I find a way to procrastinate.

Bit Wisdom

In this case, the word "bitwise" caught my attention: "XOR is a bitwise operation". I started thinking about the related phrase "bit wisdom", and wondering how much I had. Not a lot, I realized. I wasn't even sure I could define the word "bit".

I tried to catalogue my knowledge:

But all this stuff that I "know" about bits is mostly description, not definition.

In contrast to the case of the XOR illustration, Wikipedia was extremely helpful here. This is the paragraph that was most meaningful to me:

[O]ften...the words bit and binary digit are used interchangeably. But, within information theory, a bit and a binary digit are fundamentally different types of entities. A binary digit is a number that can adopt one of two possible values (0 or 1), whereas a bit is the maximum amount of information that can be conveyed by a binary digit. By analogy, a binary digit is like a container, whereas information is the amount of matter in the container.

I reduced this to Bits have states that convey information.

But that's still description, so I reduced it further: Bits are data atoms.

That sounds like a definition. Bits' state can be split into 1s and 0s, but the information they convey (on, off, etc.) is indivisible.

I was making progress on my procrastination topic, if not on the original question, but I had a new problem. Ones and zeros are opposites, as different as life and death in the context of their universe, but to me they "feel" almost identical.

0 1 0 0 1 1 0 0 1 1 0 1 1

I see them together all the time, usually right next to each other. It's like they are friends, or even closer -- siblings. How can I differentiate them so they don't just convey information in my code, but convey information for me?

Freddy and the Monolith

To distinguish zeros from ones, I noticed some differences (ones seem to have appendages, in contrast with zeros), and added some others (color, voices, energy).

My subconscious provided a representation of symmetrical, passive Zeros:

...and asymmetrical, electrified Ones:

Obi Names

I named these characters "Obis", collapsing "Anthropomorphic Bits" to "Anthropomobis" to "Mobis", then removing the M so I could distinguish individuals through different initial letters: Nobi, ..., Yobi, Zobi, etc.

After settling on "Obi" I realized this could be written 0b1, which made their name seem inevitable.

Obi Games

I imagined Obi interactions as games with well-defined rules. They might run around poking each other with NOT-shaped sticks to force each other to change state:

Or band together to play the ultimate teamwork game, AND:

Obi Characteristics

Ones Zeros

DeMorgan's Transformation Incantations

When I apply DeMorgan's Laws, I chant them like I'm casting a spell.

I say out loud, "Not p or q if and only if not p and not q" while drawing parentheses in the air with my hands. I take as long to draw the parentheses as it takes to say the phrase they contain, and make them farther apart or closer together depending on how many propositions they contain.

I do something similar for XOR truth tables, though there's less to say: "Different is True, same is False."

The echo of the words and gestures fixes the phrase in my mind while I apply it to the situation at hand. I feel like I'm temporarily drawing a cheat sheet in the air.

New challenge: Can I push my understanding of bits into the bits themselves so that they can do more of the work (and I can cast higher-level spells)?

XOR as Obi Judo

In judo competitions, one opponent commonly wears the traditional white gi and the other wears a blue one. (The belt also happens to be called an obi, which is likely why judo competitions popped into my head as an appropriate metaphor.) Competitors wear both colors as they advance in the tournament.

Let's imagine that Obi competition colors are now grey or yellow. When two Obis step onto the mat, the referee tells them whether they can compete. If they are wearing uniforms of different colors, the referee allows them to spar. If they are the same, they can't.

A transformation in symbols turns judo refereeing into the rules for XOR:

Thinking about bits as judoka waiting for a referee's permission to compete makes it easier for me to "just see" the relationship rather than having to load the ones and zeros into working memory then step through and check the truth value of each operation. I can think at a higher level of abstraction.

ABCs: Abstract Bootstrap Comics

I still haven't explained XOR swap at a deep level (for that, see Part 2), but the judo competition and colored gi metaphors show a way that might work.

I just apply XOR a few times and I'm done. Why would you spend time turning bits into characters when it's easier to just learn the rules for XOR swap and follow them?
— A critic

I originally started drawing pictures to help me remember things. But I realized that having a physical metaphor for an entity or relationship doesn't just make it more memorable, it also makes it more useful. Drawing helps me remember, but it also helps me think.

Metaphor and Narrative in Reasoning

Metaphors suggest a story. Judo Obis, for example, have goals: competitors are looking for opponents and the referees are verifying that competitors are correctly matched. These goals define their relationships, making them easier to see, remember, and reason about. They also make them more fun to think about, increasing the amount of time I'm willing to spend with them.

The right metaphor allows me to use my real-world understanding of the metaphor's vehicle to reason about its tenor. If I start with the wrong metaphor, trying to use it to reason in this way shows me where I need to improve it.

At the same time, I can offload much of my reasoning about the attributes and relationships of something I'm studying onto the representation itself, allowing me to think more abstractly. So (for me at least, and perhaps paradoxically), these concrete representations enhance abstract thinking.

Part 2 of 2: Switches on Bits

<< | < | home | > | >>