Получить детей данного родителя

Question

У меня есть набор чисел: 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#).

Answer 1

Причина, по которой она не работает для очень больших чисел, заключается в том, что вы используете double типы данных, которые ограничены точностью (около 16 цифр).

Вместо того, чтобы использовать Math.Pow и 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, вы переставляете первый бит в i-й степени 2. Вы можете адаптировать приведенный выше код, чтобы быть более похожим на ваш, и немного более эффективным, вместо того, чтобы повторять более i, просто переставляя биты parentMask в право, но тогда вы должны знать, что произойдет с отрицательными числами, и как логические сдвиги отличаются от арифметических сдвигов.