ヨセフスの問題（継子立て)

　試しに録画してテレビ番組「たけしのコマネチ大学数学科」(2006-05-26)を見てみました。
出題はヨセフスの問題(Josephus Problem)（継子立て）なるものでした。

1. １〜Ｎの番号のＮ枚のカードが順に並んた山がある
2. まず上にある１枚を山の最後へまわす
3. 次は上にある１枚を捨てる
4. １枚になるまで(ステップ2-4を)繰り返すと最後に残るカードはどの番号のカードか？

　さて、解法を飛ばして、２枚１組の場合はかなりコンピュータ向きの計算になるので、最終的な計算方法を出題の２枚１組に限定でコード(C#)にしてみました。
　Solve2はBitScanReverse(BSR)ビット〜最下位ビット(LSB)の間を１ビット左回転させていると考えることもできるようです。

using System;

namespace JosephusProblem {
	public static class Program {
		public static class JosephusProblem {
			public static int LeastExpressibleBits(ulong mask) {
				return (int)Math.Ceiling(Math.Log(mask) / Math.Log(2));
			}
			public static int BitScanReverse(ulong mask) {
				return (int)Math.Floor(Math.Log(mask) / Math.Log(2));
			}
			public static ulong Solve1(ulong numberOfCards) {
				int bits = LeastExpressibleBits((ulong)numberOfCards);
				ulong mask = (1UL << bits) - 1;
				return numberOfCards - ((~numberOfCards) & mask);
			}
			public static ulong Solve2(ulong numberOfCards) {
				ulong discards = 1UL << BitScanReverse((ulong)numberOfCards);
				return (numberOfCards - discards) * 2 + 1;
			}
		}

		public static void Main() {
			for (int i = 0; i < 63; i++) {
				ulong n = (1UL << i) + (ulong)(i * i) + 1;
				ulong x = JosephusProblem.Solve1(n);
				ulong y = JosephusProblem.Solve2(n);
				if (x != y) throw new Exception();
				Console.WriteLine("winner of {0} cards : {1} == {2}", n, x, y);
			}
			for (ulong n = 1UL << 62; n < (1UL << 63); n++) {
				ulong x = JosephusProblem.Solve1(n);
				ulong y = JosephusProblem.Solve2(n);
				if (x != y) throw new Exception();
				Console.Write("winner of {0} cards : {1}\r", n, x);
			}
		}
	}
}