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

Answer 3

Based on CodesInChaos's suggestion:

static class ExtensionMethods {
    public static string AsBits(this int b) {
        return Convert.ToString(b, 2).PadLeft(8, '0');
    }
}

class Program {
    static void Main() {
        var intArray = new[] {0, 64, 8, 8, 0, 12, 224, 0 };
        var intArray2 = (int[])intArray.Clone();
        DropDownBits(intArray2);

        for (var i = 0; i < intArray.Length; i++)
            Console.WriteLine("{0} => {1}", intArray[i].AsBits(),
                intArray2[i].AsBits());
    }

    static void DropDownBits(int[] intArray) {
        var changed = true;

        while (changed) {
            changed = false;
            for (var i = intArray.Length - 1; i > 0; i--) {
                var orgValue = intArray[i];
                intArray[i] = (intArray[i] | intArray[i - 1]);
                intArray[i - 1] = (orgValue & intArray[i - 1]);
                if (intArray[i] != orgValue) changed = true;
            }
        }
    }
}

How it works

Let's keep it simple and start with these 3 nibbles:

0) 1010
1) 0101
2) 0110

We start at the bottom row (i = 2). By applying a bitwise or with the row above (i-1) we make sure that all bits in row 2 that are 0, will become 1 if it is a 1 in row 1. So we are letting the 1-bits in row 1 fall down to row 2.

1) 0101
2) 0110

The right bit of row 1 can fall down because there is "room" (a 0) in row 2. So row 2 becomes row 2 or row 1: 0110 | 0101 which is 0111.

Now we must remove the bits that have fallen down from row 1. Therefor we perform a bitwise and on the original values of row 2 and 1. So 0110 & 0101 becomes 0100. Because the value of row 2 has changed, changed becomes true. The result so far is as follows.

1) 0100
2) 0111

This concludes the inner loop for i = 2. Then i becomes 1. Now we'll let the bits from row 0 fall down to row 1.

0) 1010
1) 0100

Row 1 becomes the result of row 1 or row 0: 0100 | 1010 which is 1110. Row 0 becomes the result of a bitwise and on those two values: 0100 & 1010 is 0000. And again, the current row has changed.

0) 0000
1) 1110
2) 0111

As you can see we aren't finished yet. That what the while (changed) loop is for. We start all over again at row 2.

Row 2 = 0111 | 1110 = 1111, row 1 = 0111 & 1110 = 0110. The row has changed, so changed is true.

0) 0000
1) 0110
2) 1111

Then i becomes 1. Row 1 = 0110 | 0000 = 0110, Row 0 = 0110 & 0000 = 0000. Row 1 hasn't changed, but the value of changed already is true and stays that way.

This round of the while (changed) loop, again something has changed, so we'll execute the inner loop once more.

This time, none of the rows will change, resulting in changed remaining false, in turn ending the while (changed) loop.

Answer 4

Count the number of 1-bits in each column. Next, clear the column and add the right number of "tokens" from the bottom.