Test a bit substring function
You test the function in the same way you test anything else: you identify some example inputs and the desired outputs, and you run the function on those inputs and see if it gives you the desired output.  You can still do that despite "not falling on a byte boundary".

In this case the function bits is a stateful interface, so you have to deal with that, but the same techniques for testing stateful interfaces should work fine here.  In particular, the "input" is a sequence of operations on the data structure / API, and the "output" is the sequence of results from those operations.  For instance, the first operation might be to set the contents of the underlying byte stream, and the second operation might be to invoke bits().

I'm not sure where you're getting $512 \times 2^{32}$ from (presumably you mean $32 \times 2^{32}$), and those aren't permutations; but in any case that doesn't change anything.  Testing almost never exhaustively tries all combinations.  I don't see why this would be any different.  Instead, the idea behind testing is that we try a small fraction of the possibilities, and if there is a bug, we hope that one of the test cases we try will expose it.  This doesn't provide any guarantees, since there could always be a bug that only triggers on one of the test cases we didn't try -- testing is not verification, and does not prove correctness -- but it is useful nonetheless.

So, nothing prevents you from testing this function.  Standard methods work fine.