Bitwise operation exercise

Question

I have the following exercise: The numbers n0 to n7 are bytes represented in binary system. The task is every bit to drop either to the bottom or if it meets another bit it stays above it. Here is a visual example:

I realized that if I apply Bitwise OR on all the numbers from n0 to n7 it's always the correct result for n7:

n7 = n0 | n1 | n2 | n3 | n4 | n5 | n6 | n7;
Console.WriteLine(n7); // n7 = 236

Unfortunately I can't think of the right way for the rest of the bytes n6, n5, n4, n3, n2, n1, n0. Do you have any ideas?

Answer 1

I wanted to come up with a solution that did not loop over the collection N times and I believe I've found a novel divide and conquer approach:

int n0_, n1_, n2_, n3_, n4_, n5_, n6_, n7_;

// Input data
int n0 = 0;
int n1 = 64;
int n2 = 8;
int n3 = 8;
int n4 = 0;
int n5 = 12;
int n6 = 224;
int n7 = 0;

//Subdivide into four groups of 2 (trivial to solve each pair)
n0_ = n0 & n1;
n1_ = n0 | n1;

n2_ = n2 & n3;
n3_ = n2 | n3;

n4_ = n4 & n5;
n5_ = n4 | n5;

n6_ = n6 & n7;
n7_ = n6 | n7;

//Merge into two groups of 4
n0 = (n0_ & n2_);
n1 = (n0_ & n3_) | (n1_ & n2_);
n2 = (n0_ | n2_) | (n1_ & n3_);
n3 = (n1_ | n3_);

n4 = (n4_ & n6_);
n5 = (n4_ & n7_) | (n5_ & n6_);
n6 = (n4_ | n6_) | (n5_ & n7_);
n7 = (n5_ | n7_);

//Merge into final answer
n0_ = (n0 & n4);
n1_ = (n0 & n5) | (n1 & n4); 
n2_ = (n0 & n6) | (n1 & n5) | (n2 & n4);
n3_ = (n0 & n7) | (n1 & n6) | (n2 & n5) | (n3 & n4);
n4_ = (n0) | (n1 & n7) | (n2 & n6) | (n3 & n5) | (n4);
n5_ = (n1) | (n2 & n7) | (n3 & n6) | (n5);
n6_ = (n2) | (n3 & n7) | (n6);
n7_ = (n3 | n7);

This approach requires just 56 bitwise operations, which is considerably fewer than the other solutions provided.

It is important to understand the cases in which bits will be set in the final answer. For example, a column in n5 is 1 if there are three or more bits set in that column. These bits can arranged in any order, which makes counting them efficiently fairly difficult.

The idea is to break the problem into sub-problems, solve the sub-problems and then merge the solutions together. Every time we merge two blocks, we know the bits will have been correctly "dropped" in each. This means we won't have to check every possible permutation of bits at each stage.

Although I didn't realize it until now, this is really similar to Merge Sort which capitalizes on sorted sub-arrays when merging.

Answer 2

This solution uses only bitwise operators :

class Program
{
    static void Main(string[] args)
    {
        int n0, n1, n2, n3, n4, n5, n6, n7;
        int n0_, n1_, n2_, n3_, n4_, n5_, n6_, n7_;

        // Input data
        n0 = 0;
        n1 = 64;
        n2 = 8;
        n3 = 8;
        n4 = 0;
        n5 = 12;
        n6 = 224;
        n7 = 0;

        for (int i = 0; i < 7; i++)
        {
            n0_ = n0 & n1 & n2 & n3 & n4 & n5 & n6 & n7;
            n1_ = (n1 & n2 & n3 & n4 & n5 & n6 & n7) | n0;
            n2_ = (n2 & n3 & n4 & n5 & n6 & n7) | n1;
            n3_ = (n3 & n4 & n5 & n6 & n7) | n2;
            n4_ = (n4 & n5 & n6 & n7) | n3;
            n5_ = (n5 & n6 & n7) | n4;
            n6_ = (n6 & n7) | n5;
            n7_ = n7 | n6;

            n0 = n0_;
            n1 = n1_;
            n2 = n2_;
            n3 = n3_;
            n4 = n4_;
            n5 = n5_;
            n6 = n6_;
            n7 = n7_;
        }

        Console.WriteLine("n0: {0}", n0);
        Console.WriteLine("n1: {0}", n1);
        Console.WriteLine("n2: {0}", n2);
        Console.WriteLine("n3: {0}", n3);
        Console.WriteLine("n4: {0}", n4);
        Console.WriteLine("n5: {0}", n5);
        Console.WriteLine("n6: {0}", n6);
        Console.WriteLine("n7: {0}", n7);
    }
}

It can be simplified though, because we don't really need to recompute all numbers : At each iteration, the top row is definitively good.

I mean this :

class Program
{

    static void Main(string[] args)
    {
        int n0, n1, n2, n3, n4, n5, n6, n7;
        int n0_, n1_, n2_, n3_, n4_, n5_, n6_, n7_;

        n0 = 0;
        n1 = 64;
        n2 = 8;
        n3 = 8;
        n4 = 0;
        n5 = 12;
        n6 = 224;
        n7 = 0;

        n0_ = n0 & n1 & n2 & n3 & n4 & n5 & n6 & n7;
        n1_ = (n1 & n2 & n3 & n4 & n5 & n6 & n7) | n0;
        n2_ = (n2 & n3 & n4 & n5 & n6 & n7) | n1;
        n3_ = (n3 & n4 & n5 & n6 & n7) | n2;
        n4_ = (n4 & n5 & n6 & n7) | n3;
        n5_ = (n5 & n6 & n7) | n4;
        n6_ = (n6 & n7) | n5;
        n7_ = n7 | n6;
        n0 = n0_;
        n1 = n1_;
        n2 = n2_;
        n3 = n3_;
        n4 = n4_;
        n5 = n5_;
        n6 = n6_;
        n7 = n7_;
        Console.WriteLine("n0: {0}", n0);
        n1_ = (n1 & n2 & n3 & n4 & n5 & n6 & n7) | n0;
        n2_ = (n2 & n3 & n4 & n5 & n6 & n7) | n1;
        n3_ = (n3 & n4 & n5 & n6 & n7) | n2;
        n4_ = (n4 & n5 & n6 & n7) | n3;
        n5_ = (n5 & n6 & n7) | n4;
        n6_ = (n6 & n7) | n5;
        n7_ = n7 | n6;
        n1 = n1_;
        n2 = n2_;
        n3 = n3_;
        n4 = n4_;
        n5 = n5_;
        n6 = n6_;
        n7 = n7_;
        Console.WriteLine("n1: {0}", n1);
        n2_ = (n2 & n3 & n4 & n5 & n6 & n7) | n1;
        n3_ = (n3 & n4 & n5 & n6 & n7) | n2;
        n4_ = (n4 & n5 & n6 & n7) | n3;
        n5_ = (n5 & n6 & n7) | n4;
        n6_ = (n6 & n7) | n5;
        n7_ = n7 | n6;
        n2 = n2_;
        n3 = n3_;
        n4 = n4_;
        n5 = n5_;
        n6 = n6_;
        n7 = n7_;
        Console.WriteLine("n2: {0}", n2);
        n3_ = (n3 & n4 & n5 & n6 & n7) | n2;
        n4_ = (n4 & n5 & n6 & n7) | n3;
        n5_ = (n5 & n6 & n7) | n4;
        n6_ = (n6 & n7) | n5;
        n7_ = n7 | n6;
        n3 = n3_;
        n4 = n4_;
        n5 = n5_;
        n6 = n6_;
        n7 = n7_;
        Console.WriteLine("n3: {0}", n3);
        n4_ = (n4 & n5 & n6 & n7) | n3;
        n5_ = (n5 & n6 & n7) | n4;
        n6_ = (n6 & n7) | n5;
        n7_ = n7 | n6;
        n4 = n4_;
        n5 = n5_;
        n6 = n6_;
        n7 = n7_;
        Console.WriteLine("n4: {0}", n4);
        n5_ = (n5 & n6 & n7) | n4;
        n6_ = (n6 & n7) | n5;
        n7_ = n7 | n6;
        n5 = n5_;
        n6 = n6_;
        n7 = n7_;
        Console.WriteLine("n5: {0}", n5);
        n6_ = (n6 & n7) | n5;
        n7_ = n7 | n6;
        n6 = n6_;
        n7 = n7_;
        Console.WriteLine("n6: {0}", n6);
        n7_ = n7 | n6;
        n7 = n7_;
        Console.WriteLine("n7: {0}", n7);
    }
}