using System;
using System.Numerics; // Allows using BigInteger
public static class Grains
{
public static ulong Square(int n)
{
switch (n)
{
case int num when num > 0 && num < 65: return (ulong)1 << (num - 1);
default: throw new ArgumentOutOfRangeException("n must be 1 through 64");
}
}
public static ulong Total()
{
return (ulong)((BigInteger.One << 64) - 1);
}
}
Instead of using math to calculate the number of grains on a square, you can simply set a bit in the correct position of a ulong
value.
To understand how this works, consider just two squares that are represented in binary bits as 00
.
You use the left-shift operator to set 1
at the position needed to make the correct decimal value.
- To set the one grain on Square One you shift
1
for0
positions to the left. So, ifn
is1
for square One, you subtractn
by1
to get0
, which will not move it any positions to the left. The result is binary01
, which is decimal1
. - To set the two grains on Square Two you shift
1
for1
position to the left. So, ifn
is2
for square Two, you subtractn
by1
to get1
, which will move it1
position to the left. The result is binary10
, which is decimal2
.
Square | Shift Left By | Binary Value | Decimal Value |
---|---|---|---|
1 | 0 | 0001 | 1 |
2 | 1 | 0010 | 2 |
3 | 2 | 0100 | 4 |
4 | 3 | 1000 | 8 |
For Total
we want all of the 64 bits set to 1
to get the sum of grains on all sixty-four squares.
The easy way to do this is to set the 65th bit to 1
and then subtract 1
.
However, we can't do this with a ulong
which has only 64
bits, so we need to use a BigInteger.
To go back to our two-square example, if we can grow to three squares, then we can shift BigInteger.One two positions to the left for binary 100
,
which is decimal 4
.
By subtracting 1
we get 3
, which is the total amount of grains on the two squares.
Square | Binary Value | Decimal Value |
---|---|---|
3 | 0100 | 4 |
Square | Sum Binary Value | Sum Decimal Value |
---|---|---|
1 | 0001 | 1 |
2 | 0011 | 3 |
Shortening
When the body of a function is a single expression, the function can be implemented as an expression-bodied member, like so
public static ulong Total() =>
(ulong)((BigInteger.One << 64) - 1);
or
public static ulong Total() => (ulong)((BigInteger.One << 64) - 1);