C# · 12月 29, 2021

c# – 按位操作练习

我有以下练习:数字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 dataint 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 4n0 = (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 answern0_ = (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.这些位可以以任何顺序排列,这使得它们的计数效率相当困难.

这个想法是将问题分解为子问题,解决子问题,然后将解决方案合并在一起.每次我们合并两个块时,我们知道这些位将被正确地“丢弃”.这意味着我们不必在每个阶段检查每一个可能的位排列.

尽管到目前为止,我并没有意识到,这与合并排序相似,它合并后排序的子数组.