Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
FizzBuzz solved using only bit twiddling. It essentially uses two deterministic finite automata for divisibility testing.
#include <stdio.h>
int f0(unsigned int x) { return x? (x&(1<<31)? f1(x<<1) : f0(x<<1)) : 1; }
int f1(unsigned int x) { return x? (x&(1<<31)? f3(x<<1) : f2(x<<1)) : 0; }
int f2(unsigned int x) { return x? (x&(1<<31)? f0(x<<1) : f4(x<<1)) : 0; }
int f3(unsigned int x) { return x? (x&(1<<31)? f2(x<<1) : f1(x<<1)) : 0; }
int f4(unsigned int x) { return x? (x&(1<<31)? f4(x<<1) : f3(x<<1)) : 0; }
int t0(unsigned int x) { return x? (x&(1<<31)? t1(x<<1) : t0(x<<1)) : 1; }
int t1(unsigned int x) { return x? (x&(1<<31)? t0(x<<1) : t2(x<<1)) : 0; }
int t2(unsigned int x) { return x? (x&(1<<31)? t2(x<<1) : t1(x<<1)) : 0; }
int main(void) {
unsigned int i;
for(i=1; i <= 100; i++) {
if(t0(i)) printf("Fizz");
if(f0(i)) printf("Buzz");
if(!(t0(i)|f0(i))) printf("%u",i);

Kudos for effort! Now write that on a whiteboard within 5 minutes within your job interview 😄


grantslatton commented Oct 28, 2013

I could write the deterministic finite automata that the functions emulate pretty quickly! Writing out the C implementation might take a bit longer...


Now try it using only NAND operations :D

void main() should be int main(void).

If you're using a C book that tells you to use void main(), its author doesn't know the language very well; find a better one.

Now let's see if I can port this to javascript ...


grantslatton commented Oct 28, 2013

Keith-S-Thompson: Fixed. Been coding too much Java recently.

Peaker commented Oct 28, 2013

Don't use "unsigned int" when you want a 32-bit uint, that's what uint32_t is for.

gryftir commented Oct 29, 2013

I believe you can use
if(f0(i)) printf("Buzz");
else if(!(t0(i)) printf("%u",i);

which lets you avoid testing f0 twice.

now that you've changed it from void to int, "return 0;" as a success :)

skmasq commented Oct 29, 2013

@gryftir but then numbers you'll get Fizz3 as first result

ebobby commented Oct 29, 2013

@robert-wallis the C99 standard says that return 0 is implicit in your main. You do not need to add it. Unless you are compiling with a C90 compiler that is.

Wow, that is truly, hideously, unmaintainable.

pkallos commented Oct 29, 2013

@bradchoate I wonder who's maintaining fizzbuzz code IRL; I don't think that's the point of this exercise :).

korczis commented Oct 29, 2013

Something for grammar nazis:

That is cute. I've never understood why fizzbuzz is such a thing. But doing it with finite automata, and without division, is cool.

If you can tolerate Ruby, here's a boring fizzbuzz in six lines, with zap (7) thrown in. I don't know what's under the covers in the "step" function, but this shouldn't use anything but addition and array increment. It does have an array. I've never used a programming language that didn't have arrays (and that's going back to the early 70s). I like my spaces after "Fizz" and "Buzz". Didn't bother to make this a gist.

a =
0.step(100, 3) { |i| a[i] = a[i].to_s + "Fizz " }
0.step(100, 5) { |i| a[i] = a[i].to_s + "Buzz " }
0.step(100, 7) { |i| a[i] = a[i].to_s + "Zap " }
a.each_index {|i| a[i] = i if a[i] == nil }
puts a

Now, if I wanted to make a production version, I'd pull the 0.steps into a function, and pass in the array size on the command line. But you knew that :-)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment