Programming Notes Fall 25

Bit Hacking

Definition of two’s compliment

-x == ~x + 1

Really handy if (for some reason), you only have unsigned integers at your disposal and need signed arithmetic. A natural consequence of the identity is:

A-B == A + ~B + 1

Or, less apparent

A-B == ~(~A+B)

Which is shown to be true by expanding

~x = -x -1

A-B == -(~A+B)-1
    == -(-A-1+B)-1
    ==   A+1-B-1
    ==   A-B 

Graphs

A graph consists of nodes (vertices) and connections (edges).

Lets say we have five nodes, (1,5), with the following connections

1<=>3
5<=>2
5<=>3
2<=>4
4<=>5

A few ways to represent this graph

Representation as a list of connections Per Node

The simplest method and easiest to query is store each node in a list with a sublist of connections for that node.

graph = [
    [3],
    [4,5],
    [1,5],
    [2,5],
    [2,3,4],
]

Representation as bitsets/a binary matrix

Alternatively, a list of bitsets can be used to enumerate the connections. Each set bit represents a connection to the node with the id of the bit index.

graph = [
    0b00100,
    0b11000,
    0b10001,
    0b10010,
    0b01110,
]