phanerozoic / threshold-ctz8

threshold-ctz8

8-bit count trailing zeros (CTZ). Returns the number of trailing zero bits before the first set bit. Returns 8 if input is zero.

Circuit

 x7  x6  x5  x4  x3  x2  x1  x0
  │   │   │   │   │   │   │   │
  └───┴───┴───┴───┴───┴───┴───┘
              │
              ▼
    ┌─────────────────────┐
    │  Priority Detect    │    Layer 1-3
    │  (find first 1)     │
    └─────────────────────┘
              │
              ▼
    ┌─────────────────────┐
    │  Position Encoder   │    Layer 4-5
    │  (binary encoding)  │
    └─────────────────────┘
              │
              ▼
        [c2, c1, c0]
        (count 0-7)

    Plus: all_zero detector for count=8

Function

ctz8(x7, x6, x5, x4, x3, x2, x1, x0) -> (c3, c2, c1, c0)

where c = 4*c3 + 2*c2 + c1 + c0 = number of trailing zeros

If x0 is set, count = 0. If only x7 is set, count = 7. If no bits set, count = 8.

Truth Table (selected)

Mechanism

Step 1: Find first set bit from LSB

Detect positions where a bit is set and all lower bits are zero:

Step 2: Encode position to binary

• c0 = p1 OR p3 OR p5 OR p7 (odd positions)
• c1 = p2 OR p3 OR p6 OR p7 (positions 2,3,6,7)
• c2 = p4 OR p5 OR p6 OR p7 (positions 4-7)
• c3 = pZ (all zeros → count = 8)

Architecture

Parameters

Usage

from safetensors.torch import load_file
import torch

w = load_file('model.safetensors')

def ctz8(bits):
    # bits = [x0, x1, x2, x3, x4, x5, x6, x7] (LSB first)
    inp = torch.tensor([float(b) for b in bits])

    c0 = int((inp @ w['c0.weight'].T + w['c0.bias'] >= 0).item())
    c1 = int((inp @ w['c1.weight'].T + w['c1.bias'] >= 0).item())
    c2 = int((inp @ w['c2.weight'].T + w['c2.bias'] >= 0).item())
    c3 = int((inp @ w['c3.weight'].T + w['c3.bias'] >= 0).item())

    return c3, c2, c1, c0

# Examples
print(ctz8([1,0,0,0,0,0,0,0]))  # (0,0,0,0) = 0 trailing zeros
print(ctz8([0,0,0,0,1,0,0,0]))  # (0,1,0,0) = 4 trailing zeros
print(ctz8([0,0,0,0,0,0,0,0]))  # (1,0,0,0) = 8 trailing zeros (all zero)

Applications

• Finding alignment in memory addresses
• Bit manipulation in compression algorithms
• Finding least significant set bit
• Integer factorization (powers of 2)
• Loop optimization

Related Circuits

• threshold-clz8 : Count leading zeros (mirror operation)
• threshold-ffs8 : Find first set (similar, 1-indexed)
• threshold-priorityencoder8 : Finds MSB position instead

Files

threshold-ctz8/
├── model.safetensors
├── model.py
├── create_safetensors.py
├── config.json
└── README.md

License

MIT