algorithm - 通过对 A 和 B(含)之间的一个或多个整数进行按位或运算，可以生成多少个不同的数字

Question

通过对 A 和 B(含)之间的一个或多个整数进行按位或运算，可以生成多少个不同的数字？

解释:
在这种情况下，A=7 和 B=9。对 {7, 8, 9} 的非空子集进行按位或运算可以生成四个整数:7, 8, 9 和 15
1≤A≤B<2^60

我的做法:
将给定的两个数字都转换为二进制。遍历它们并试图形成不同的条件。但我没有得到不同整数的数量。请帮我解决如何为此开发算法和程序。

Answer 1

首先，用二进制表示数字，用零填充两者到相同的位数。例如，如果 A = 7 和 B = 9，那么这将给出 0111 和 1001 。

接下来，从左侧(最高有效位)开始迭代，直到找到两个数字不同的位置。忽略左边的所有位置。 (它们无关紧要，因为它们对于范围内的所有值具有相同的位，因此对于范围内的任何值的按位或运算，它们也具有相同的位。)如果您没有找到这样的位置，则A = B，答案是 1。如果你找到了这样的位置，那么 A 在那个位置有一个 0，B 在那个位置有一个 1。

由于我们忽略了它们不同的第一个左侧的所有位置，让我们假设这些位置中的位都是 0 。这给我们留下了 A < 2n ≤ B，其中 n 是那个位的位置。 (例如，7 < 23 ≤ 9。)

现在，范围 [A, B] 中的任何一组值都属于以下三种情况之一:

案例#1: 它可能仅由范围 [A, 2n - 1] 中的值组成，这意味着位置 n 处的位对于其每个元素都是 0。

如果对 [A, 2n − 1] 中的任何一组值进行按位或运算，您仍然会在 [A, 2n − 1] 中得到一个值:一组正整数的按位或运算永远不会小于这些整数中的最大值，并且在位置 n(或更高)处没有 1 的集合的按位或将永远不会在位置 n(或更高)处有 1。 (如果这些事实一开始看起来并不明显，我建议您尝试一些值，直到您明白它们为什么正确为止。)

相反，对于 [A, 2n - 1] 中的每个值，您可以轻松构造一个集合，其按位或就是该值:具体而言，您可以将包含该值的集合作为其唯一元素。

因此，这些集合的所有不同按位或的集合是 [A, 2n - 1]。

案例#2: 它可能仅由范围 [2n, B] 中的值组成，这意味着位置 n 处的位对于其每个元素都是 1。

这种情况有点棘手。要解决它，请找到 B 中位置 n 右侧的第一个 1 位。称该位置为 m。 (例如，如果 B 是 1001_0011 并且 n 是 7 -slash- 2n 是 1000_0000 ，那么 m 是 4 -slash- 2m 是 0001_0000 。)

现在，对于这个范围内的每个值，位置 m 左边的每一位都是 0 ，除了位置 n 的位是 1 ；所以你永远不能构造一个按位或将超出范围 [2n, 2n + 2m+1 - 1] 的集合。

此外，对于位置 m 处或右侧的每个位置 k，2n + 2k 都在 [2n, B] 范围内。 (例如，如果 2n 是 1000_0000 并且 B 是 1001_0011 ，那么 1001_0000 、 1000_1000 、 1000_0100 、 1000_0010 、 1000_0001 、 1000_0000 和 2 n 之间的所有值都是 1 和 2 之间的所有值，即 B 1 和 2 0 4 和 2 之间的任何值，2 和 2 − 1](例如，将是 [ 1001_1111 , 1 ] )，您可以构造一个集合，其按位或就是那个值，只需选择每个元素都有两个 1 s——一个在位置 n，一个在另一个位置你需要。

因此，这些集合的所有不同按位或的集合是 [2n, 2n + 2m+1 - 1]。

Case #3: 它可能由范围 [A, 2n - 1] 中的一个或多个值和范围 [2n, B] 中的一个或多个值组成。

这种情况可能看起来更棘手，但由于按位或是可交换和关联的(我们一直依赖于此:否则“集合的按位或”的整个前提将是模棱两可的)，按位或这种集合的按位或等于其与范围 [A, 2n - 1] 的交集的按位或与其与范围 [2n, B] 的交集的按位或。 (例如，{7,8,9} 的按位或等于 7 和 9 的按位或，其中 7 是 {7} 的按位或，9 是 {8 的按位或， 9}。)因此，使用案例 #1 和案例 #2 的结果，我们知道这样一个集合的按位或是来自 [A, 2n - 1] 的任何元素和来自 [ 2n, 2n + 2m+1 - 1]，其中 m 的定义与情况 #2 相同。

现在，这些按位或运算必须在 [2n + A, 2n+1 - 1] 范围内:

它们不能小于 2n + A，因为它们必须在位置 n 处具有 1，并且在位置 n 的右侧，它们必须具有 [A, 2n - 1] 中某个数字的所有 1 位。

它们不能大于 2n+1 - 1，因为这需要 0000_0101 位于位置 n 左侧的某处。

相反，[2n + A, 2n+1 - 1] 范围内的每个值都是 2n 和 [A, 2n - 1] 范围内数字的按位或。

因此，这些集合的所有不同按位或的集合是 [2n + A, 2n+1 - 1]。

因此，结合这三种情况，我们需要 [A, 2n − 1]、[2n, 2n + 2m+1 − 1] 和 [2n + A, 2n+1 − 1] 的并集，其中(合并第一个二) 是 [A, 2n + 2m+1 − 1] 和 [2n + A, 2n+1 − 1] 的并集。请注意，这两个范围可能会重叠，但无论哪种方式都非常简单:如果范围重叠，则我们合并它们，否则我们不合并，并且范围 [x, y] 中的元素数量为 y - x + .

它们重叠的一个示例:如果A是 1001_0011和B是 0000_0101，那么我们需要[ 1001_1111， 1000_0101]和[ 1111_1111， 0000_0101]的结合，这是指[ 1111_1111， 0001_0011]，即[5,1 255]，其中包含251 个元素。

它们不重叠的一个例子:如果 A 是 1000_0101 并且 B 是 0001_0011 ，那么我们需要 [ 1000_0111 , 1001_0011 ] 和 [ 1111_1111 , 5,910 ] , 5, 5, 5, 5, 5, 5, 4, 5, 4, 4 的并集分别包含 117 和 108 个元素，总共 225 个元素。

下面是这种方法在 C 中的实现。(将它移植到任何模糊的类 C 语言应该很简单，例如 C++、Java、C#、JavaScript 或 Perl。)

int find_leftmost_differing_bit(uint64_t const A, uint64_t const B) {
  int shift = 0;
  while ((A >> shift) != (B >> shift)) {
    ++shift;
  }
  return shift - 1;
}

int find_leftmost_1bit_to_right_of(uint64_t const B, int const n) {
  for (int m = n - 1; m >= 0; --m) {
    if ((B >> m) % 2 == 1) {
      return m;
    }
  }
  return -1;
}

uint64_t do_it_fast(uint64_t const A, uint64_t const B) {
  if (A == B) {
    return 1;
  }
  int const n = find_leftmost_differing_bit(A, B);
  int const m = find_leftmost_1bit_to_right_of(B, n);
  uint64_t const shared_bits = ((A >> (n + 1)) << (n + 1));
  uint64_t const case_1_lower_bound = A;
  uint64_t const case_2_upper_bound =
    shared_bits + (1 << n) + (1 << (m + 1)) - 1;
  uint64_t const case_3_lower_bound = A + (1 << n);
  uint64_t const case_3_upper_bound = shared_bits + (1 << (n + 1)) - 1;
  if (case_2_upper_bound < case_3_lower_bound - 1) {
    return (case_3_upper_bound - case_3_lower_bound + 1)
         + (case_2_upper_bound - case_1_lower_bound + 1);
  } else {
    return case_3_upper_bound - case_1_lower_bound + 1;
  }
}

如您所见，实现本身比确定它给出正确结果的所有论证要短得多。

该函数被称为 do_it_fast 是因为，作为完整性检查，我还编写了一个名为 do_it_slow(如下)的版本，它直接构建了集合，并确认这两个函数对于所有 0 ≤ A ≤ B < 29 都给出相同的结果。没必要也就是说，对于大 B， do_it_fast 比 do_it_slow 快得多；在我的机器上，一旦 B 达到大约 100,000，即使是对 do_it_slow 的一次调用也需要相当长的时间。

unsigned int do_it_slow(unsigned int const A, unsigned int const B) {
  unsigned int const upper_bound = B == 0 ? 0 : B * 2 - 1;
  bool possible[upper_bound+1];
  for (unsigned int i = 0; i <= upper_bound; ++i) {
    possible[i] = (i >= A && i <= B);
  }
  unsigned int result = B - A + 1;
  for (unsigned int i = A; i <= upper_bound && i < B * 2; ++i) {
    if (possible[i]) {
      for (unsigned int j = A; j <= upper_bound; ++j) {
        if (possible[j] && ! possible[i|j]) {
          possible[i|j] = true;
          ++result;
        }
      }
    }
  }
  return result;
}