1 files changed, 86 insertions, 0 deletions
diff --git a/trees/blog/binbin-tree.typ b/trees/blog/binbin-tree.typ
new file mode 100644
index 0000000..c8b51e6
--- /dev/null
+++ b/trees/blog/binbin-tree.typ
@@ -0,0 +1,86 @@
+#import "html_elements.typ": post
+#show: post
+
+#import "@preview/cetz:0.4.2"
+#import "./lib.typ": flex, svg_inline
+
+
+= The trick
+I really like tricks with binary numbers. This one I was using to test digital systems.
+
+
+#html.frame()[
+
+  #cetz.canvas({
+    import cetz.draw: *
+
+    let max_depth = 7
+    let cols = calc.pow(2, max_depth)
+
+    let total_size = 10
+    let cell_width = total_size / cols
+    let cell_height = total_size / max_depth
+
+    let colors = (
+      oklab(80%, 50%, 30%),
+      oklab(80%, 0%, 50%),
+      oklab(80%, -50%, 0%),
+    )
+
+
+    for line in range(max_depth) {
+      for col in range(cols) {
+        if int.bit-and(col, calc.pow(2, line)) != 0 {
+          rect(
+            (col * cell_width, -line * cell_height),
+            ((col + 1) * cell_width, -(line + 1) * cell_height),
+            fill: colors.at(calc.rem(line, colors.len())),
+            stroke: none,
+          )
+        }
+      }
+    }
+  })
+]
+
+So, were does this come from? Is this generated by some *slow* recursive algorithm? No! This complete binary tree is generated by this code:
+
+```c
+if (col & (1 << line)) != 0 {
+    *pixel = c[line % c.len()];
+}
+```
+
+= How it works
+So, how does this work? Well, let's count binary numbers.
+
+```
+111
+110
+101
+100
+
+011
+010
+001
+000
+```
+
+The leftmost bit changes every four lines, the middle bit every two lines and the rightmost every other line. From this pattern it's clear that every combination of the three bits will be generated once, for this reason and because it's very easy to generate I was using it to test my digital circuit.
+
+But how do we generate these numbers? Just count from 0 up to #box()[#html.frame[#text(fill: white)[$2^n - 1$]]]. So in this case from 0 to 7:
+
+```
+000 = 0
+001 = 1
+010 = 2
+011 = 3
+100 = 4
+101 = 5
+110 = 6
+111 = 7
+```
+
+= The tree
+This is also a complete binary tree. If you think about it as a decision tree, it may be easier to see the reason why. The first bit can be either true of false, for each case the second bit can be true or false too; if one is true, it is highlighted, otherwise it's black. The number of different leaves is exactly the number of all possible binary strings with `H` bits, where `H` is equal to the height of the tree.
+