logo标签列表

位运算练习

c#bit-manipulationbitwise-or
10

我有以下练习：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
从底部向上迭代，查看连续的一对行。用这两行的二进制AND替换上面的行，用这两行的二进制OR替换下面的行。重复此过程，直到没有任何移动为止。 - CodesInChaos
4
或者迭代每一列，在使用(n[i]>>column)&1提取并计算1位时，然后将该数量的1位从底部填充到该列中。 - CodesInChaos
4个回答
11

我希望提出一种解决方案，不需要对集合进行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非常相似，后者在合并时利用了排序的子数组。

3

这个解决方案只使用位运算符：

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 技术，但我们并不需要重新计算所有数字，因此可以进行简化：

每次迭代时，顶部行就已经是确定的好行了。

我的意思是：

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);
    }
}
我知道会有简单的解决方案...谢谢@hoang！我喜欢你的方法。 - Todo
2

统计每一列中1的位数。接下来，清空该列并从底部添加相应数量的“令牌”。

我曾考虑过这个选项，但我的知识不足以实现它。我的意思是，假设n0到n7的字节是一个数组的元素。在我们将数组的每个元素转换为二进制后，我们得到了这个： 00000000 01000000 00001000 00001000 00000000 00001100 11100000 00000000 我们如何按列处理位？ - Todo
我猜你需要循环遍历行并提取每一列。另一种方法是，首先将值转换为二维布尔数组，进行操作，然后再转换回去。虽然不够高效，但也许仍然是更好的解决方案。 - usr
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;
            }
        }
    }
}

它是如何工作的

让我们保持简单，从这三个要点开始：

0) 1010
1) 0101
2) 0110

我们从底部行开始（i = 2）。通过将位或应用于上一行（i-1），我们确保第2行中所有为0的位，如果在第1行中为1，则会变为1。因此，我们让第1行中的1位下降到第2行。
1) 0101
2) 0110

第一行的右边一位可能会下降，因为第二行有“空位”（一个0）。所以第二行变成了第一行或第二行：0110 | 0101，即0111。
现在我们必须从第一行中删除已经下降的位。因此，我们对第二行和第一行的原始值执行按位与操作。因此，0110 & 0101变成了0100。由于第二行的值已更改，changed变为true。 到目前为止的结果如下。
1) 0100
2) 0111

内部循环结束，i = 2。 然后 i 变成1。现在我们让第0行的位向下掉到第1行。

0) 1010
1) 0100

第一行成为第一行或第零行的结果：0100 | 1010，即1110。第零行成为这两个值的按位与的结果：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)循环。

谢谢，comecme！它很好用，虽然对我来说有点复杂 :) - Todo
我曾试图解释它的工作原理。然而，正如人们经常说的那样，如果你的代码需要这么多的解释，那就太复杂了。 - comecme
我已经不需要将结果转换为字节。一开始我使用的是 byte。但是两个字节进行位运算的结果是一个 int。这就是为什么我不得不使用 (byte)(byteArray[i] | byteArray[i-1])。 - comecme
感谢详细的解释。现在清楚了。我之前缺失的是基本概念：第N行=第N行|第N-1行；第N-1行=第N行&第N-1行； - Todo
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接