Search code examples
bit-manipulationbitwise-operators

How to do bitwise logic for fitting box


I'm not good in bit logic but I think it will be the best solution for my problem.

I have to find if an object can fit in a box, I won't consider 3D rotation but just simple 90° options. So basically if the object can fit in any way inside the box.

I'm actually checking all the dimensions of the object against the dimensions of the box, so I know if ObjWidth can fit in BoxWidth OR BoxLength OR BoxHeight and so on with ObjLength and ObjHeight. This is defined using a Flag enum for each dimension

enum En_Dimension
    {
        None = 0,
        Width = 1,
        Lenght = 2,
        Height = 4,
        All = Width | Length| Height,
    }

So I can have (that means that it fit on that side):

width = Width | Length | Height  /// 111
length = Width                   /// 001
height = Width                   /// 001  

basically my method should be something like

bool FitIn (Size container)
{
    En_Dimension width = En_Dimension.None; 
    En_Dimension length = En_Dimension.None;
    En_Dimension height = En_Dimension.None;

    for(var do in this.Dimensions){
        for (var db in container.Dimensions){
            if (do <= db) {
               // already implemented code to
               // SET width OR length OR height
            }
        }
    }

    /// EXAMPLES
    /// 001     001
    /// 110     001
    /// 010     111
    /// FIT     DON'T FIT

    return (/*width, length, height BIT LOGIC*/) == En_Dimension.All
}

The expected output of the example is false while it should return true only when it "fit" on all the lines in at least one not already fitted side. Let's say this are the "valid" combination of ones

1**    1**    *1*    *1*    **1    **1
*1*    **1    1**    **1    1**    *1*
**1    *1*    **1    1**    *1*    1**

Solution

  • It could be done with 6 tests, corresponding to each of the permutations:

    int fittingDims = (int)width | ((int)length << 4) | ((int)height << 8);
    return (fittingDims & 0x124) == 0x124 ||
           (fittingDims & 0x142) == 0x142 ||
           (fittingDims & 0x214) == 0x214 ||
           (fittingDims & 0x241) == 0x241 ||
           (fittingDims & 0x412) == 0x412 ||
           (fittingDims & 0x421) == 0x421;
    

    There are no octal literals in C# so I used 4 bits per "block" to make the constants nice in hexadecimal.