Binary path-counting gadget
= Binary path-counting gadget
A binary path-counting gadget replaces an edge of nonnegative integer weight $w$ by a zero-one directed graph with exactly $w$ routes from its entrance to its exit. Repeated doubling and conditional addition follow the binary expansion of $w$ using only linearly many vertices in its bit length.