需要一个快速函数，该函数使用按位运算上升然后下降

本文关键字：函数 运算上 然后 一个 | 更新日期: 2023-09-27 18:30:37

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

0 1

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

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

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

作为不起作用的示例，这是我的金字塔函数，以及我对绝对值的实现：

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();
}

此金字塔函数创建序列，例如 0 1 2 3 4 5 6 5 4 3 2 1 0

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

我有一个想法，将查找表存储为长整型或 BigInteger 中的连续位块，并将它们移出并屏蔽掉，但这会占用长序列的太多内存。不过，它使用很少的指令。

需要一个快速函数，该函数使用按位运算上升然后下降

试试这个：

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

结果：

01234566543210

结果获得如下：

                  ' 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
金字塔

是问题中定义的原始金字塔方法。

函数：

public static long Ziggurat(this long N, long max)
{
  N = max - N;
  return max - (N ^ N >> -1);
}

没有循环、测试或分支。只需要四次操作;两个是按位的。

但是，您的问题有问题。您指定的输出为：

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

此序列有 14 个元素。但是，您还可以将函数的范围指定为"0 到 2* max"，其中只有 13 个元素！我认为零到2 * max + 1的范围是可以接受的。

而且，这是一个基于控制台的测试：

static void Main(string[] args)
{
  long max = 6;
  for (long i = 0; i <= 2 * max + 1; i++)
  {
    Console.Write("{0} ", i.Ziggurat(max));
  }
}

和输出：

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

N = max - N行使输入值从最大值倒计时到数字线的负侧，从而使范围0 through 13变为6 through -7。

请注意以下几点：

  • -1 的按位补码是 0 （~11111111 = 00000000）。
  • -7 的按位补码是 6 （~11111001 = 00000110）。

因此，如果我们从 6 计数到 -7 并补充所有负值，我们得到这个序列，其中包括两个零：

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

第二行的子表达式N ^ N >> -1补充N，但只有当N为负时。

第二行中表达式的其余部分max - …将上述序列反转为所需的输出：

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

∎

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;
    }
}

人们可能会用Concat Enumerable.Range和可能的选择/反向或类似的东西来计算整个事情，但它的效率可能会略低，因为我不知道有什么微不足道的倒计时方法。 反向将比 yielding for 循环更"工作"，并且选择（最大值减去Enumerable.Range的当前迭代）将做一堆额外的算术，所有这些都是为了避免几行代码。

即：

public static IEnumerable<long getPyramid(long maxValue)
{
  return Enumerable.Range(0, maxValue)
  .Concat(Enumerable.Range(0, maxValue).Select(num => maxValue - num));
}
相关文章：