`popcnt(x) < tzcnt(x)` asks the question "does `x` have fewer set bits than it has trailing zeroes". It's a simple question with a simple answer, but cute enough to think about on a Sunday morning.[1]

Here are the solutions for 8 bits, in order: 0, 4, 8, 16, 24, 32, 40, 48, 64, 72, 80, 96, 112, 128, 136, 144, 160, 176, 192, 208, 224[2]

In case you find decimal hard to do read (as I do), here they are again in binary: 00000000, 00000100, 00001000, 00010000, 00011000, 00100000, 00101000, 00110000, 01000000, 01001000, 01010000, 01100000, 01110000, 10000000, 10001000, 10010000, 10100000, 10110000, 11000000, 11010000, 11100000

Simply staring at the values doesn't do much for me. To get a better handle on what's going on, let's recursively (de-)construct the set of `n`-bit solutions.

The most significant bit of an `n`-bit solution is either 0 or 1:

- If it is 0, then that bit affects neither the
`popcnt`nor the`tzcnt`so removing it must yield an`(n-1)`-bit solution. - If it is 1, then removing it along with the least significant bit (which must be zero, there are no odd solutions since their
`tzcnt`would be zero) would decrease the both`popcnt`and the`tzcnt`by 1, yielding an`(n-2)`-bit solution.

This "deconstructive" recursion is slightly awkward. The constructive version would be: you can take the `(n-1)`-bit solutions and prepend a zero to them, and you can take the `(n-2)`-bit solutions and prepend a one and append a zero to them. However, it is less clear then (to me anyway) that those are the *only* `n`-bit solutions. The "deconstructive" version starts with all `n`-bit solutions and splits them into two obviously-disjoint groups, removing the possibility of solutions getting lost or being counted double.

The `F(n) = F(n - 1) + F(n - 2)` structure of the number of solutions is clear, but there are different sequences that follow that same recurrence that differ in their base cases. Here we have 1 solution for 1-bit integers (namely zero) and 1 solution for 2-bit integers (also zero), so the base cases are 1 and 1 as in the Fibonacci sequence.

This is probably all useless, and it's barely even bitmath.

[1] Or whenever, but it happens to be a Sunday morning for me right now.

[2] This sequence does not seem to be on the OEIS at the time of writing.