按位和正

Question

我在解决一个问题，它说明我们需要找到所有最小数的和，这些最小数需要添加到数组中的元素中，以使按位和大于0。

我的方法是：首先，我决定在所有元素中找到最右边集合的位置，并检查要添加的总的最小数目，以便and大于零。但这是行不通的，有谁能帮我找到另一种Algo吗？

Answer 1

让我们先解决一个有点不同的问题：

为确保第k位置的第1（从零开始），应向值添加最小分钟数？

我们这里有两个案例：

   min = 100...000000000 - (value & 11.....11111)
          <- k zeroes ->            <- k ones ->

代码(C#)

  private static long AddToEnsureOne(long value, int position) {
    if ((value & (1L << position)) != 0)
      return 0;

    long shift = 1L << (position);

    return shift - (value & (shift - 1)); 
  }

演示：如果我们有3并且我们希望1在第二个位置

   0b011
     ^
     we want 1 here

我们应该加上

   0b100 - (0b011 & 0b11) == 4 - 3 == 1

  private static long MinToAdd(IEnumerable<int> items) {
    long best = 0;

    for (int i = 0; i < 32; ++i) {
      long sum = 0;

      foreach (int item in items)
        sum += AddToEnsureOne(unchecked((uint)item), i); // uint - get rid of sign

      if (i == 0 || sum < best)
        best = sum;
    }

    return best;
  }

简单测试：

  Console.Write(MinToAdd(new int[] { 4, 4, 3, 2}));

结果：

  3