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
[1msignedoverflow.cc:16:9: [31mruntime error:[30m signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'[m
```

**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

`~` |
output |
---|---|

0 | 1 |

1 | 0 |

`&` |
0 | 1 |
---|---|---|

0 | 0 | 0 |

1 | 0 | 1 |

`|` |
0 | 1 |
---|---|---|

0 | 0 | 1 |

1 | 1 | 1 |

`^` |
0 | 1 |
---|---|---|

0 | 0 | 1 |

1 | 1 | 0 |

## 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 * 2`

^{i}

- Like
`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 / 2`

rounded down^{i}

- If
- 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

- For instance, every integer whose decimal representation ends in
- Others are weirder!

## Fun with bits

- What general property is tested by
`(x & 1) == 0`

?- It tests whether
`x`

is even

- It tests whether
- 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 & (2`

≡^{i}- 1))`x`

mod`2`

, but is much faster to compute^{i}

- 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

- Whether
- 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`

!

- The value of the lowest 1 bit in

## 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`

- For example, ℬ(
- 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))

- ℬ(X ∖ Y) = (ℬ(X)
- 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;
}
```