c# - 位运算练习

Question

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

Answer 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。这些位可以按任何顺序排列，这使得对它们进行有效计数变得相当困难。

想法是将问题分解成子问题，解决子问题，然后将解决方案合并在一起。每次合并两个 block 时，我们都知道每个 block 中的位都已正确“丢弃”。这意味着我们不必在每个阶段检查所有可能的位排列。

虽然直到现在我才意识到，这确实类似于合并排序时合并时利用已排序子数组的合并排序。