Data representation 5: Undefined behavior and bits

Overview

We explore undefined behavior in more depth and discuss bitwise arithmetic.

Readings on undefined behavior

Undefined behavior and abstract machine

Broad-brush model of programmer psychology

People want their code to:

  1. Work relatively correctly on most inputs
  2. Run fast
  3. Work exactly correctly on all inputs

Why?

Compiler quality

The as-if rule

Undefined behavior

How undefined behavior and optimizing compilers collide

Example 1: Signed integer overflow

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

Example 2: Null pointer dereference

static void __devexit agnx_pci_remove (struct pci_dev *pdev)
{
  struct ieee80211_hw *dev = pci_get_drvdata(pdev);
  struct agnx_priv *priv = dev->priv; 

  if (!dev) return;

Example 3: Signed integer overflow in a loop

long sum = 0;
for (int i = n1; i <= n2; ++i) {
    sum += f(i);
}
return sum;

Example 4: Out-of-bounds access

int awesome[4] = {0, 1, 2, 3};

bool is_awesome(int v) {
    for (int i = 0; i <= 4; ++i) {
        if (awesome[i] == v)
            return true;
    }
    return false;
}

More examples of undefined behaviors

What to do?

Bitwise operators

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

Some mathematical properties

Left and right shift

Aside: Sized integer types

Fun with bits

Fun with bits (2)

Using bits

Bitset example

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 hacksGosper’s hack