c# - 按位运算练习

我进行以下练习: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的正确方法。
你有什么想法？

最佳答案

我想提出一个解决方案，该解决方案不会遍历整个馆藏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，它在合并时会利用已排序的子数组。

关于c# - 按位运算练习，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13628191/