2

我需要一个整数值函数，它返回一个升序，直到它达到给定的最大值，然后再次下降。我称它为Ziggurat：

0 1 2 3 4 5 6 6 5 4 3 2 1 0

步骤都是一个。最大值（在序列的中间）必须出现两次。在零到最大 2* 的范围之外，我不在乎会发生什么。

我希望函数快速 - 没有分支。我更喜欢按位运算。

作为一个不起作用的例子，这是我的 Pyramid 函数，以及我的绝对值实现：

private static readonly int LONG_ABS_MASK_SHIFT = sizeof(long) * 8 - 1;

/// <summary>
/// Compute the Absolute value of a long without branching.
/// 
/// Note: This will deviate from Math.Abs for Int64.MinValue, where the .NET library would throw an exception.
/// The most negative number cannot be made positive.
/// </summary>
/// <param name="v">Number to transform.</param>
/// <returns>Absolute value of v.</returns>
public static long Abs(this long v)
{
    long mask = v >> LONG_ABS_MASK_SHIFT;
    return (v ^ mask) - mask;
}

public static long Pyramid(this long N, long max)
{
    return max - (max - N).Abs();
}

这个 Pyramid 函数创建像 0 1 2 3 4 5 6 5 4 3 2 1 0 这样的序列

请注意，中间的数字只出现一次。

我有一个想法，将查找表存储为 long 或 BigInteger 中的连续位块，并将它们移位和屏蔽掉，但这对于长系列来说占用了太多内存。不过，它使用的指令很少。

4

3 回答 3

3

尝试这个：

public static long Pyramid2(this long N, long max)
{
    return N.Pyramid(max + 1) + ((max - N) >> -1);
}

结果：

0 1 2 3 4 5 6 6 5 4 3 2 1 0

结果如下：

                  \ N=0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18
  N.Pyramid(6 + 1)    0  1  2  3  4  5  6  7  6  5  4  3  2  1  0 -1 -2 -3 -4
+ ((max - N) >> -1)   0  0  0  0  0  0  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
=                     0  1  2  3  4  5  6  6  5  4  3  2  1  0 -1 -2 -3 -4 -5

Pyramid 是问题中定义的原始Pyramid方法。

于 2012-04-11T02:23:37.360 回答
2
于 2012-04-11T05:28:39.520 回答
1 
public static IEnumerable<long> getPyramid(long maxValue)
{
    for(long i = 0; i <= maxValue; i++)
    {
        yield return i;
    }

    for(long i = maxValue; i >=0; i--)
    {
        yield return i;
    }
}

一个人可能会使用 select/reverse 或类似的东西来处理整个事情Concat Enumerable.Range，但它的效率可能会稍微低一些，因为我不知道让它倒计时的简单方法。反向将比产生 for 循环更多“工作”，并且选择（执行 maxvalue 减去 的当前迭代Enumerable.Range）将执行一堆额外的算术，所有这些都是为了避免几行代码。

IE：

public static IEnumerable<long getPyramid(long maxValue)
{
  return Enumerable.Range(0, maxValue)
  .Concat(Enumerable.Range(0, maxValue).Select(num => maxValue - num));
}
于 2012-04-11T02:11:12.510 回答