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.
(n[i]>>column)&1, then fill that number of 1 bits from the bottom into the column. – Quartas