Битовое упражнение
У меня есть следующее упражнение: числа от n0 до n7 - это байты, представленные в двоичной системе. Задача состоит в том, чтобы каждый бит опускаться либо вниз, либо, если он встречает другой бит, он остается над ним. Вот наглядный пример:
Я понял, что если я применяю побитовое ИЛИ ко всем числам от n0 до n7, это всегда правильный результат для n7:
n7 = n0 | n1 | n2 | n3 | n4 | n5 | n6 | n7;
Console.WriteLine(n7); // n7 = 236
К сожалению, я не могу придумать правильный путь для остальных байтов n6, n5, n4, n3, n2, n1, n0. Есть ли у вас какие-либо идеи?
4 ответа
Я хотел найти решение, которое не будет повторять коллекцию N раз, и я считаю, что нашел новый подход "разделяй и властвуй":
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);
Этот подход требует всего 56 побитовых операций, что значительно меньше, чем у других предоставляемых решений.
Важно понимать случаи, в которых биты будут установлены в окончательном ответе. Например, столбец в n5 равен 1, если в этом столбце установлено три или более битов. Эти биты могут быть расположены в любом порядке, что затрудняет их эффективный подсчет.
Идея состоит в том, чтобы разбить проблему на подзадачи, решить подзадачи, а затем объединить решения вместе. Каждый раз, когда мы объединяем два блока, мы знаем, что биты будут правильно "сброшены" в каждом. Это означает, что нам не нужно проверять каждую возможную перестановку битов на каждом этапе.
Хотя я не осознавал этого до сих пор, это действительно похоже на сортировку слиянием, которая при объединении извлекает выгоду из отсортированных подмассивов.
Это решение использует только побитовые операторы:
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);
}
}
Это может быть упрощено, потому что нам не нужно пересчитывать все числа: на каждой итерации верхняя строка определенно хороша.
Я имею в виду это:
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);
}
}
Подсчитайте количество 1-бит в каждом столбце. Далее очистите столбец и добавьте нужное количество "жетонов" снизу.
На основании предложения CodesInChaos:
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;
}
}
}
}
Как это устроено
Давайте будем простыми и начнем с этих 3-х кусочков:
0) 1010
1) 0101
2) 0110
Мы начинаем с нижнего ряда (я = 2). Применяя побитовую или указанную выше строку (i-1), мы гарантируем, что все биты в строке 2, равные 0, станут 1, если это будет 1 в строке 1. Таким образом, мы разрешаем 1-бит в строке 1 упасть на ряд 2.
1) 0101
2) 0110
Правый бит строки 1 может упасть, потому что есть "комната" (0) в строке 2. Таким образом, строка 2 становится строкой 2 или строкой 1: 0110 | 0101 который 0111,
Теперь мы должны удалить биты, выпавшие из строки 1. Для этого мы выполняем побитовые и исходные значения строк 2 и 1. Так 0110 & 0101 становится 0100, Поскольку значение строки 2 изменилось, changed становится true, Результат пока таков.
1) 0100
2) 0111
Это завершает внутренний цикл для i = 2. Тогда i становится 1. Теперь мы позволим битам из строки 0 опуститься до строки 1.
0) 1010
1) 0100
Строка 1 становится результатом строки 1 или строки 0: 0100 | 1010 который 1110, Строка 0 становится результатом побитового и этих двух значений: 0100 & 1010 является 0000, И снова текущая строка изменилась.
0) 0000
1) 1110
2) 0111
Как видите, мы еще не закончили. Это то, что while (changed) петля для. Мы начинаем все сначала со строки 2.
Ряд 2 = 0111 | 1110 = 1111строка 1 = 0111 & 1110 = 0110, Строка изменилась, поэтому changed является true,
0) 0000
1) 0110
2) 1111
затем i становится 1. Ряд 1 = 0110 | 0000 = 0110, Строка 0 = 0110 & 0000 = 0000, Строка 1 не изменилась, но значение changed уже есть true и остается таким.
Этот раунд while (changed) цикл, опять что-то изменилось, поэтому мы выполним внутренний цикл еще раз.
На этот раз ни одна из строк не изменится, в результате чего changed остальной falseв свою очередь окончание while (changed) петля.