Count Fancy Numbers

For the original problem description, pls checkout the image source at the very bottom of this web page 🐾🐾

Imagine you’re in a magical world where certain numbers are considered "fancy." A number is fancy if, when written in base-4, it only contains the digits 0 and 1—like secret codes known only to wizards. For example, 17 is fancy because its base-4 form, 101, uses only 0s and 1s, while 18 is not, as its base-4 form, 102, contains a forbidden 2. Now, your task is to discover how many of these special, fancy numbers exist below a given number, n. But beware! n can be as big as a billion, so you need a clever method—something faster than just checking every number individually.