我有以下练习：数字n0到n7是二进制系统中的字节.这个任务有点落到底部,如果它遇到另一个位,它保持在它的上方.这是一个视觉示例：
我意识到,如果我对从n0到n7的所有数字应用按位OR,那么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.这些位可以以任何顺序排列,这使得它们的计数效率相当困难.
这个想法是将问题分解为子问题,解决子问题,然后将解决方案合并在一起.每次我们合并两个块时,我们知道这些位将被正确地“丢弃”.这意味着我们不必在每个阶段检查每一个可能的位排列.
尽管到目前为止,我并没有意识到,这与合并排序相似,它合并后排序的子数组.
