Fizzbuzz bitwise math

fizz.rb

messages = [nil, "Fizz", "Buzz", "FizzBuzz"]
acc = 810092048
(1..100).each do |i|
  c = acc & 3
  puts messages[c] || i
  acc = acc >> 2 | c << 28
end

# Explanation
#
# "810092048" appears to be a magic number, but if we display it as binary
# pairs it starts to make sense:
pairs = 810092048.to_s(2).scan(/.{2}/)
#=> ["11", "00", "00", "01", "00", "10", "01", "00", "00", "01", "10", "00", "01", "00", "00"]
# Now display each pair of binary digits as decimal:
pairs = pairs.map {|x| x.to_i(2)}
#=> [3, 0, 0, 1, 0, 2, 1, 0, 0, 1, 2, 0, 1, 0, 0]
# Now map those to messages:
pairs.map {|x| messages[x]}
#=> ["FizzBuzz", nil, nil, "Fizz", nil, "Buzz", "Fizz", nil, nil, "Fizz", "Buzz", nil, "Fizz", nil, nil]
# Notice that this is a reversed version of the first 15 messages (where nil
# stands for "pass through the integer") in the FizzBuzz sequence.

# Now for the binary math. `acc & 3` is the same as taking the last binary pair
# of the number, because 3 == "11" in binary. So `c = acc & 3` just grabs the
# last binary pair of acc. `c` must be 0, 1, 2, or 3, so we print messages[c]
# or pass through the integer if the message is nil (c == 0). Then we perform
# some shifting on acc. Notice that acc is 30 binary digits long:
810092048.to_s(2).length
#=> 30

# So if we shift acc to the right 2 digits, we "pop off" the last (rightmost)
# binary pair. That's `acc >> 2`. However, if we want to keep the sequence
# going past the first 15 integers, we really need to push the binary pair we
# just used back onto the end of the stack. So, we use a binary OR of the
# shifted acc with c (the last index we used) shifted to the right 28 binary
# digits. That way the sequence can go on forever!

# Let's see what that looks like for one of the iterations, to make it more
# clear. First let's make a helper function to print out these binary numbers.
def pp_binary(n)
  # pad up to 30 binary digits for consistency
  (("0" * 30) + n.to_s(2))[-30..-1].scan(/.{2}/).join(' ')
end

# Here's our magic number...
acc = 810092048
# But let's start by shifting off the first two pairs (4 digits), since we know
# those are both zero, so those iterations don't show us much.
acc = acc >> 4
#=> 50630753
# Let's see that in binary for reference:
pp_binary(acc)
#=> "00 00 11 00 00 01 00 10 01 00 00 01 10 00 01"

# Now let's see what our index is. We're on the iteration for 3, so we should
# have the index for "Fizz", which is 1.
c = acc & 3
pp_binary(c)
#=> "00 00 00 00 00 00 00 00 00 00 00 00 00 00 01"

# Looks good. Now let's see what acc looks like when we shift it over 2
# digits...
pp_binary(acc >> 2)
#=> "00 00 00 11 00 00 01 00 10 01 00 00 01 10 00"
# Notice that the last pair has been shifted off, and the leftmost pair is now
# zero.

# To get that last pair back, we take c and shift it back 28 digits:
pp_binary(c << 28)
#=> "01 00 00 00 00 00 00 00 00 00 00 00 00 00 00"

# Great! Now we just combine those with a binary OR.
acc = acc >> 2 | c << 28
# The binary OR sets each digit to 1 if it is 1 in either of the operands.
pp_binary(acc)
#=> "01 00 00 11 00 00 01 00 10 01 00 00 01 10 00"
# So now we've pushed our last pair back onto acc, and we're ready to run the
# process again! Whew!