按位操作练习

Question

我有以下练习:数字n0到n7是二进制系统中表示的字节.任务是一点点掉到底部,或者如果它遇到另一个位,它会保持在它之上.这是一个视觉示例:

我意识到如果我对从n0到n7的所有数字应用Bitwise OR,它总是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 .这些位可以按任何顺序排列,这使得有效地计算它们相当困难.

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

虽然直到现在我才意识到这一点,但这与Merge Sort非常相似,它在合并时利用了排序的子数组.

Answer 2

计算每列中 1 位的数量。接下来，清除该列并从底部添加正确数量的“令牌”。