0

我有一组数字：1、2、4、8、16、32、64 等。

现在给定一个数字，比如说 44，我必须确定它有 32、8 和 4 个孩子。（32 + 8 + 4 = 44）

到目前为止，我有以下代码：

   public static long[] GetBTreeChildren(long? parentMask)
    {            
        var branches = new List<long>();
        if (parentMask == null) return branches.ToArray();

        double currentValue = (double)parentMask;            

        while (currentValue > 0D)
        {
            double power = Math.Floor(Math.Log(currentValue, 2.0D));

            double exponentResult = Math.Pow(2, power);

            branches.Add((long)exponentResult);

            currentValue -= exponentResult;
        }

        return branches.ToArray();
    }

但是当给定的数字非常大时（例如 36028797018963967），上面的代码不起作用

我正在使用 VS2012 (C#)。

4

1 回答 1

1

它不适用于非常大的数字的原因是因为您使用double的是精度有限的数据类型（大约 16 位）。

无需使用Math.Powand Math.Log，您需要的一切都可以通过简单、极其高效的按位运算来完成。

public static long[] GetBTreeChildren(long? parentMask)
{            
    var branches = new List<long>();
    if (parentMask == null) return branches.ToArray();

    for(int i = 0; i < 63; ++i)
    {
        if( (parentMask & (1L << i)) != 0)
            branches.Add(1L << i);
    }            

    return branches.ToArray();
}

基本上，每一位已经是 2 的幂，这就是你要找的。通过这样做(long) 1 << i，您将第一位移动到 2 的第 i 次幂。您可以调整上面的代码，使其与您的代码更相似，并且效率更高，而不是迭代i，只需将parentMask的位向右移动，但是你必须知道负数会发生什么，以及逻辑移位与算术移位有何不同。

于 2013-06-08T05:13:52.230 回答