Побитовая операция
У меня есть следующее упражнение: числа от n0 до n7 представляют собой байты, представленные в двоичной системе. Задача состоит в том, чтобы каждый бит отбрасывался либо снизу, либо если он встречает другой бит, он остается над ним. Вот наглядный пример:
![enter image description here]()
Я понял, что если я применяю побитовое ИЛИ для всех чисел от n0 до n7, то всегда правильный результат для n7:
n7 = n0 | n1 | n2 | n3 | n4 | n5 | n6 | n7;
Console.WriteLine(n7); // n7 = 236
К сожалению, я не могу думать о правильном пути для остальных байтов n6, n5, n4, n3, n2, n1, n0.
У вас есть идеи?
Ответы
Ответ 1
Я хотел придумать решение, которое не зацикливалось на коллекции 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, если в этом столбце есть три или более бита. Эти биты могут располагаться в любом порядке, что делает их достаточно эффективными.
Идея состоит в том, чтобы разбить проблему на подзадачи, решить подзадачи, а затем объединить решения вместе. Каждый раз, когда мы объединяем два блока, мы знаем, что бит будет правильно "отброшен" в каждом. Это означает, что нам не нужно проверять каждую возможную перестановку бит на каждом этапе.
Хотя я до сих пор не осознавал этого, это действительно похоже на Merge Sort, который использует заархивированные сортированные подмассивы при слиянии.
Ответ 2
В этом решении используются только побитовые операторы:
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);
}
}
Ответ 3
Подсчитайте количество 1 бит в каждом столбце. Затем очистите столбец и добавьте нужное количество "токенов" снизу.
Ответ 4
На основе предложения 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
Мы начинаем в нижней строке (i = 2). Применяя поразрядный или с приведенной выше строкой (i-1), мы убеждаемся, что все биты в строке 2, которые равны 0, станут 1, если это 1 в строке 1. Таким образом, мы даем 1 бит в строке 1 упасть до строки 2.
1) 0101
2) 0110
Правильный бит строки 1 может упасть, потому что в строке 2 есть "комната" (a 0). Так что строка 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).
