Instantly share code, notes, and snippets.

# grantslatton/fizzbuzz.c Last active Aug 21, 2017

FizzBuzz solved using only bit twiddling. It essentially uses two deterministic finite automata for divisibility testing.
 #include 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); printf("\n"); } }

### philrykoff commented Oct 28, 2013

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

### 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...

 Nice!

### JamesDunne commented Oct 28, 2013

 Now try it using only NAND operations :D

### Keith-S-Thompson commented Oct 28, 2013

 `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.

### mikelyons commented Oct 28, 2013

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

### 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.

### robert-wallis commented Oct 29, 2013

 now that you've changed it from void to int, "return 0;" as a success :) http://www.gnu.org/software/libc/manual/html_node/Exit-Status.html

### 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.

### bradchoate commented Oct 29, 2013

 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: http://www.slideshare.net/olvemaudal/deep-c

### mikeloukides commented Apr 26, 2015

 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 = Array.new(100) 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 :-)