Last active
August 19, 2022 11:20
-
-
Save grantslatton/7187941 to your computer and use it in GitHub Desktop.
FizzBuzz solved using only bit twiddling. It essentially uses two deterministic finite automata for divisibility testing.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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"); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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 :-)