And, in addition, it seems to me that if you do the full conversion, then you might be able to reduce considerably the number of numbers that you need to check. Suppose for example that, in base 4, you find one number to be 20000001. Then you know that there is no point to check any number between 20000001(4) and 33333333(4), as none of them is a likely candidate to be made of only 0's and 1's.
This huge optimization might be possible without doing the full conversion, but it looks far less easy.