CODEWITHSUNDEEP
c#binary-tree
Kymel15
Kymel15

Reputation: 15

Get the children of a given parent

I have a set of numbers: 1,2,4,8,16,32,64,etc.

Now given a number let say 44, I have to identify that it has children 32, 8 and 4. (32 + 8 + 4 = 44)

What I have so far is the following code:

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

But the code above is not working when a given number is very large (e.g. 36028797018963967)

I am using VS2012 (C#).

Upvotes: 0

Views: 58

Answers (1)

i Code 4 Food
i Code 4 Food

Reputation: 2154

The reason it does not work for very large numbers, is because you are using double data types, which are limited in precision (about 16 digits).

Instead of using Math.Pow and Math.Log, everything you need can be done with simple, extremelly more efficient, bitwise operations.

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

Basically, each bit is already a power of 2, which is what you are looking for. By doing (long) 1 << i you are shifting the first bit to the i'th power of 2. You can adapt the code above to be more similar to yours, and slightly more efficient, by instead of iterating over i, simply shifting parentMask's bits to the right, but then you must be aware of what would happen to negative numbers, and how logical shifts differ from arithmetic shifts.

Upvotes: 1

Related Questions