NOT A is the same as A XOR 1

12 November 2023

why

I was recently intrigued hearing Chris Lattner (the creator of Swift) talking with Lex about how an Int in Swift is just a struct defined in the Swift Standard Library, rather than something built into Swift (the language).

"Int and Float (and also Array and String and things like this) — These are all part of the [Swift Standard] Library. Like, Int is not hard-coded into Swift" — Chris Lattner

This is awesome, because it means you can create your own types with the same tools used to create one of the most ubiquitous types in any programming language: the integer.

This reminds me of the original LittleBigPlanet, where they created all the main story levels with the same level creation tools you can use when building your own custom levels. So cool.

This made me want to peek at the standard library's source code, which I'd never done.

what

Looking for an easily digestible file, I found Bool.swift, which was only 343 lines long! I noticed that in order to implement the NOT (!) operator, it just uses XOR with 1:

extension Bool {
  @_transparent
  public static prefix func ! (a: Bool) -> Bool {
    return Bool(Builtin.xor_Int1(a._value, true._value))
  }
}

I've never thought about the NOT operator like this, but it totally works!

how

XOR

XOR (exclusive OR) is an operator that compares two binary (true or false) values, returns true if they're different, and false if they're the same. It's a bit easier to see if we draw a Karnaugh map (or K-map for short), which lays out all possible inputs and outputs of the XOR operator. Inputs are in the left column and top row — the other cells are the result of applying the XOR operator to any two inputs. Oh, also: false is 0, and true is 1.

⬇ A `XOR` B ⮕	0	1
0	`0`	`1`
1	`1`	`0`

NOT

NOT, often written as !, is an even simpler operator. It just flips the input. !1 is 0, and !0 is 1.

NOT via XOR

If you ignore the middle column of that table, and just look at 0 XOR 1, and 1 XOR 1, you can see that it does exactly what the NOT operator does: it flips the inputs.

⬇ A `XOR` B ⮕	1
0	`1`
1	`0`

Looky there, that's the same as NOT A! nice.

`!`A
0	`1`
1	`0`

result

So, in order to implement NOT A (aka !A), the Swift Standard Library authors used a standard bitwise operator (XOR), by using A XOR 1.

To be clear, I'm not sure why they did this. I just found it interesting, and maybe you will too.

bonus — light switches

XOR is a really cool operator. It's used for all sorts of things. It has a unique property that if you change any single one of the inputs, the output changes.

For example, have you ever been in a room that has two light switches for one light, and wondered how that worked? A circuit version of XOR is how that works. Any time you flip a switch, it changes the state of the light.

This can be a bit unsatisfying to logic-loving folk, because then there's no inherent meaning of "on" and "off" when you look at the switch, but it's undoubtedly the way to go, as the real design goal here is to be able to toggle the light from two locations, which this accomplishes beautifully.

If you're extra bothered by this, you could install push button switches. They don't have any visible state of their own. They're also incredibly satisfying to press.

Here's a K-map showing how this works:

⬇ switch 1 `XOR` switch 2 ⮕	down	up
down	🌚	🌝
up	🌝	🌚

Note that it could also be configured like this, which achieves the same behavior from the user perspective:

⬇ switch 1 `XOR` switch 2 ⮕	down	up
down	🌝	🌚
up	🌚	🌝

How is this circuit actually implemented in real life? I may have a degree in electrical engineering, but I'm no electrician. I have no clue.

Previous: Birth of blog