CS Ramble — Set 2d - boolean logic

This is post is part of set 2 of A Ramble Around CS.

In this post, we’re going to become more familiar with messing around with individual bits: “bit twiddling”.

And, Or, Not, etc.

When dealing with bits—or with “boolean” values (True or False)1—we talk about value a and value b, value a or value b, etc. They have more precise meanings than their normal English usage:

In normal usage, you might say, “I’ll wash the dishes if you take the trash out and feed the dog.“ The first part (washing the dishes) will be true if both (taking the trash out) and (feeding the dog) are true. This actually corresponds pretty much exactly to boolean values:

a b   a and b
False False False
False True False
True False False
True True True

Using 1 to represent True, and 0 for False, we could also write that like so:

a b   a and b
0 0 0
0 1 0
1 0 0
1 1 1

In English, though, when we say, “I’m going to take the trash out or feed the dog,” we usually mean we’ll do one or the other, but not both.2

With boolean logic, “or” doesn’t imply that both won’t be true. Here’s the truth table:

a b   a or b
False False False
False True True
True False True
True True True

And again with 0 and 1 (which we’ll stick to from now on):

a b   a or b
0 0 0
0 1 1
1 0 1
1 1 1

The word for “a or b, but not both” is called “exclusive or” (“xor”), and means what it sounds like:

a b   a xor b
False False False
False True True
True False True
True True False

There’s one more basic boolean operation: not:

a   not a
0 1
1 0

An aside: circuits and gates

In an electrical circuit, we call the components that perform these operations “gates”, and use the following symbols:

A guick search yielded a decent YouTube video on simple gates. To see a more complex example of how to combine several gates to do something useful, go to this site and choose the “4-bit addition” preset.

“ANDing” and “ORing” bits

Just as we can and together two bits, we can and together two numbers each made up of many bits: we just perform the and bit by bit:

a 0 1 0 1 0 1 1 0
b 1 0 1 1 0 0 1 0
a and b 0 0 0 1 0 0 1 0

Same with or:

a 0 1 0 1 0 1 1 0
b 1 0 1 1 0 0 1 0
a or b 1 1 1 1 0 1 1 0

xor:

a 0 1 0 1 0 1 1 0
b 1 0 1 1 0 0 1 0
a or b 1 1 1 0 0 1 0 0

not:

a 0 1 0 1 0 1 1 0
not a 1 0 1 0 1 0 0 1

In Go code, these operations would use & for and, | for or, ^ for xor, and a prefixed ^ for not (most languages use a prefixed ~):

var a uint8 = 0b01010110
var b uint8 = 0b10110010

fmt.Printf("a:       %08b\n", a)
fmt.Printf("b:       %08b\n", b)
fmt.Printf("a and b: %08b\n", a&b)
fmt.Printf("a or b:  %08b\n", a|b)
fmt.Printf("a xor b: %08b\n", a^b)
fmt.Printf("not a:   %08b\n", ^a)

/*
a:       01010110
b:       10110010
a and b: 00010010
a or b:  11110110
a xor b: 11100100
not a:   10101001
*/

(playground version here)

In Python, it would look very similar:

a = 0b01010110
b = 0b10110010

print(f'a:       {a:08b}')
# a:       01010110

print(f'b:       {a:08b}')
# b:       01010110

print(f'a and b: {a&b:08b}')
# a and b: 00010010

print(f'a or b:  {a|b:08b}')
# a or b:  11110110

print(f'a xor b: {a^b:08b}')
# a xor b: 11100100

# For not, we have to force the result back into the range [0,255].
# (If the highest bit in a number is set, the number is
# interpreted as a negative number.)
print(f'not a:   {~a % 256:08b}')
# not a:   10101001


In the next part, we’ll learn how to read and change the values of individual bits.

1. Named after George Boole ↩︎

2. Although, of course, if I said, “I’ll wash the dishes if you take the trash out or feed the dog,“ and you did both, I’d still wash the dishes! ↩︎