Data representation 6: Assertions and arenas

This lecture started out with a 30-minute discussion of assertion style. We referred to the CS 61 Style Guide several times, and the concept of “Goldilocks assertions”: not too many, not too few. A concrete question was raised about unused functions; the [[maybe_unused]] attribute was introduced.

Example 1: Signed integer overflow

int x_incr = x + 1;
assert(x_incr > x);
printf("assertion passed, so %d > %d\n", x_incr, x);

• ./signedoverflow 1 prints?
  • assertion passed, so 2 > 1
• Compiled without optimization by clang++, ./signedoverflow 2147483647 prints?
  • signedoverflow.cc:17: int main(int, char **): Assertion `x_incr > x' failed.
  • Because 2147483647 + 1 == -2147483648 in signed computer integer arithmetic!
• Compiled with optimization, ./signedoverflow 2147483647 prints?
  • assertion passed, so -2147483648 > 2147483647

Sanitizer to the rescue

• Compilers with sanitizers have a different goal—making the code run as fast as possible, while detecting undefined behavior

$ make SAN=1 signedoverflow
...
$ ./signedoverflow 2147483647
signedoverflow.cc:16:9: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'

• Always check your code with sanitizers!

Sanitizers and undefined behavior

• Our makefiles allow you to compile with make SAN=1
• This turns on sanitizers, which are efficient checkers that catch many undefined behaviors
• Other powerful tools: valgrind, tis-interpreter, etc.

Using computer arithmetic for good

• A bitwise operator is one that operates on the bits of its input(s) independently
• C and C++ bitwise operators:
  • ~ (unary): complement
  • &: bitwise and
  • |: bitwise or
  • ^: bitwise exclusive or
  • <<: left shift
  • >>: right shift

Truth tables

Beware precedence

• C did not pick the right precedence for bitwise operators
• x & 1 != 0 is parsed as x & (1 != 0)
• Most uses of bitwise operators require parentheses

Some mathematical properties

• &, |, and ^ are commutative: (a&b)==(b&a)
• &, |, and ^ are associative: (a&(b&c))==((a&b)&c)
• & and | are distributive: ((a&b)|(a&c)) == (a&(b|c)), ((a|b)&(a|c)) == (a|(b&c))
• & distributes over ^: ((a&b)^(a&c)) == (a&(b^c))
• 0 is the identity for | and ^: (x|0)==x, (x^0)==x
• -1 (=~0) is the identity for &: (x&-1)==x
• 0 is the absorbing or annihilating element for &: (x&0)==0
• -1 is the absorbing element for |: (x|-1)==-1

Left and right shift

• a << i: Move the bits in a left by i places, shifting in 0s
  • Like a = a * 2i
• a >> i: Move the bits in a right by i places
  • If a is unsigned, shifting in 0s
  • If a is signed, shifting in copies of the sign bit
  • Like a = a / 2i rounded down
• On many computers, left and right shift are much faster than multiplication and (especially) division
• i must be nonnegative and less than 8 * sizeof(a)

Properties of bitwise arithmetic

• Powers of 2 are very important in computer systems programming
• Binary number representation means bitwise expressions often correspond to other interesting properties
• Some of these properties are analogous to decimal
  • For instance, every integer whose decimal representation ends in 0 is a multiple of 10
• Others are weirder!

Fun with bits

• What general property is tested by (x & 1) == 0?
  • It tests whether x is even
• Can you define unary negation -x using other operators (bitwise and +)?
  • -x ≡ ~x + 1
• What does x & 15 equal in normal arithmetic?
  • x % 16
  • In general, (x & (2i - 1)) ≡ x mod 2i, but is much faster to compute
• What’s the mathematical intuition behind the expression x - (x & 15)?
  • x rounded down to the nearest multiple of 16
  • Like (x / 16) * 16, but likely faster
  • Equivalent to x & ~15!
• What can you learn about x from the value x & (x - 1)?
  • Whether x is a power of two. (x & (x - 1)) == 0 iff x is 0 or a power of 2
• What does x & -x equal?
  • The value of the lowest 1 bit in x
  • (5 & -5) == 1; (10 & -10) == 2; (8 & -8) == 8
  • In unsigned arithmetic, it’s also the gcd (greatest common divisor) of x and -x!

Using bits

• Bitwise operators allow us to efficiently represent small sets
• A set is a collection of elements, each of which might be present or absent
• An integer is a collection of bits, each of which might be 1 or 0
• Set operations, such as union, intersection, and membership-test, correspond to bitwise operations

Bitset example

• Consider sets taken from the universe {e, f, g, h}
• Assign each element m a distinct bit value ℬ(m) (which must be a power of two)
  • For example, ℬ(e) = 1, ℬ(f) = 2, ℬ(g) = 4, ℬ(h) = 8
• A set of elements is represented as the sum of the ℬ values
  • ℬ({}) =
  • ℬ({}) = 0
  • ℬ({e, g}) =
  • ℬ({e, g}) = ℬ(e) + ℬ(g) = 5
  • ℬ({e, f, g, h}) =
  • ℬ({e, f, g, h}) = 15
• Union and intersection
  • ℬ(X ∪ Y) =
  • ℬ(X ∪ Y) = (ℬ(X) | ℬ(Y))
  • ℬ(X ∩ Y) =
  • ℬ(X ∩ Y) = (ℬ(X) & ℬ(Y))
  • Map to bitwise & and |!
  • For example, {e, f} ∪ {e, h} = {e, f, h}, and indeed (3 | 9) == 11
• Set difference maps to & with ~
  • ℬ(X ∖ Y) = (ℬ(X) & ~ℬ(Y))
• Membership testing maps to &
  • m ∈ X ⟺ (ℬ(m) & ℬ(X)) != 0

WTF corner

(You don’t need to understand this, but it is fun!)

unsigned long wtf(unsigned long x) {
    unsigned long y = x & -x;
    unsigned long c = x + y;
    return (((x ^ c) >> 2) / y) | c;
}

Bit twiddling hacks — Gosper’s hack