Create a gist now

Instantly share code, notes, and snippets.

Embed
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);
printf("\n");
}
}
@philrykoff

This comment has been minimized.

Show comment
Hide comment
@philrykoff

philrykoff Oct 28, 2013

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

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

@grantslatton

This comment has been minimized.

Show comment
Hide comment
@grantslatton

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

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

@brianherman

This comment has been minimized.

Show comment
Hide comment

Nice!

@JamesDunne

This comment has been minimized.

Show comment
Hide comment
@JamesDunne

JamesDunne Oct 28, 2013

Now try it using only NAND operations :D

Now try it using only NAND operations :D

@Keith-S-Thompson

This comment has been minimized.

Show comment
Hide comment
@Keith-S-Thompson

Keith-S-Thompson 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.

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

This comment has been minimized.

Show comment
Hide comment
@mikelyons

mikelyons Oct 28, 2013

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

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

@grantslatton

This comment has been minimized.

Show comment
Hide comment
@grantslatton

grantslatton Oct 28, 2013

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

Owner

grantslatton commented Oct 28, 2013

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

@Peaker

This comment has been minimized.

Show comment
Hide comment
@Peaker

Peaker Oct 28, 2013

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

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

This comment has been minimized.

Show comment
Hide comment
@gryftir

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

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

This comment has been minimized.

Show comment
Hide comment
@robert-wallis

robert-wallis 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

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

This comment has been minimized.

Show comment
Hide comment
@skmasq

skmasq Oct 29, 2013

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

skmasq commented Oct 29, 2013

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

@ebobby

This comment has been minimized.

Show comment
Hide comment
@ebobby

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

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

This comment has been minimized.

Show comment
Hide comment
@bradchoate

bradchoate Oct 29, 2013

Wow, that is truly, hideously, unmaintainable.

Wow, that is truly, hideously, unmaintainable.

@pkallos

This comment has been minimized.

Show comment
Hide comment
@pkallos

pkallos Oct 29, 2013

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

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

This comment has been minimized.

Show comment
Hide comment

korczis commented Oct 29, 2013

Something for grammar nazis: http://www.slideshare.net/olvemaudal/deep-c

@mikeloukides

This comment has been minimized.

Show comment
Hide comment
@mikeloukides

mikeloukides 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 :-)

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 :-)

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