Josephus Problem

bench.rb

#!/usr/bin/env ruby
require 'benchmark/ips'

def who_will_live_1?(n)
  a = 1
  begin
    a <<= 1
  end until a > n
  2*n - a + 1
end

def who_will_live_2?(n)
  a = 1
  while true do
    if a > n
      return 2*(n - (a >> 1)) + 1
    end
    a <<= 1
  end
end

def who_will_live_3?(n)
  1.step do |a|
    return 2*(n - 2**a) + 1 if 2**(a + 1) > n
  end
end

def who_will_live_4?(n)
  l = nil
  1.step do |a|
    if 2**(a + 1) > n
      l = n - 2**a
      break
    end
  end
  2*l + 1
end

def who_will_live_5?(n)
  n.to_s(2).chars.rotate.join.to_i(2)
end

Benchmark.ips do |x|
  x.config(:time => 5, :warmup => 2)

  x.report("1") do
    1.upto 10_000 do |n|
      who_will_live_1? n
    end
  end

  x.report("2") do
    1.upto 10_000 do |n|
      who_will_live_2? n
    end
  end

  x.report("3") do
    1.upto 10_000 do |n|
      who_will_live_3? n
    end
  end

  x.report("4") do
    1.upto 10_000 do |n|
      who_will_live_4? n
    end
  end

  x.report("5") do
    1.upto 10_000 do |n|
      who_will_live_5? n
    end
  end

  x.compare!
end;

Josephus.rb

#!/usr/bin/env ruby
#
# Josephus Problem
# https://www.youtube.com/watch?v=uCsD3ZGzMgE
#
def who_will_live?(n)
  a = 1
  begin
    a <<= 1
  end until a > n
  2*n - a + 1
end

who_will_live?(41) # => 19