时间戳

首页 > 解决方案 > 通过对 A 和 B（含）之间的一个或多个整数进行按位或运算可以生成多少个不同的数字

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

问题描述

通过对 A 和 B（包括）之间的一个或多个整数进行按位或运算可以生成多少个不同的数字？

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

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

标签： algorithmdata-structuresnumbers

解决方案

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

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

由于我们忽略了它们不同的第一个左侧的所有位置，因此我们假设这些位置中的位都是0. 剩下的就是A  < 2 n  ≤  B，其中n是该位的位置。（例如，7 < 2 3  ≤ 9。）

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

  • 情况 #1：它可能仅由 [ A , 2 n  - 1] 范围内的值组成，这意味着位置n处的位0适用于其每个元素。
    • 如果你对 [ A , 2 n - 1] 中的任何一组值进行按位或运算，你 仍然会在 [ A , 2 n - 1] 中得到一个值：一个集合的 按位或正整数的 永远不会小于这些整数中的最大值，并且在位置 n（或更高）处没有 s 的集合的按位或将永远不会在位置n（或更高）处具有 a。（如果这些事实一开始看起来并不明显，我建议尝试一些值，直到你明白为什么它们是正确的。）11
    • 相反，对于 [ A , 2 n  − 1] 中的每个值，您可以轻松地构造一个按位或为该值的集合：具体而言，您可以将包含该值的集合作为其唯一元素。
    • 因此，这些集合的所有不同按位或的集合是 [ A , 2 n  - 1]。
  • 情况 #2：它可能仅包含 [2 n , B ] 范围内的值，这意味着位置n处的位适用1于它的每个元素。
    • 这个案例有点棘手。为了解决这个问题，找到B中位置n1右侧的第一位。称那个位置为 m。（例如，如果B是且n是 7 -slash- 2 n is ，则m是 4 -slash- 2 m is 。）1001_00111000_00000001_0000
    • 现在，对于这个范围内的每个值，位置m左侧的每个位都是0，除了位置n的位，即1; 所以你永远不能构造一个按位或将超出范围 [2 n , 2 n  + 2 m +1  - 1] 的集合。
    • 此外，对于位置 m 处或右侧的每个位置k，2 n +  2 k都在范围 [2 n , B ] 内。（例如，如果 2 n是并且B是，那么, , , , 和都在 2 n和B之间。）所以这意味着对于范围 [2 n , 2 n  + 2 m +1  -  ;1] （这将是 [ ,1000_00001001_00111001_00001000_10001000_01001000_00101000_00011000_00001001_1111] 例如），您可以构造一个按位或为该值的集合，只需选择每个都有两个1s 的元素 - 一个在位置n，一个在您需要的另一个位置。
    • 因此，这些集合的所有不同按位或的集合是 [2 n , 2 n  + 2 m +1  - 1]。
  • 案例#3：它可以由[ A , 2n-  1]范围内的一个或多个值和[ 2n , B ]范围内的一个或多个值组成。
    • 这种情况可能看起来更棘手，但由于按位或是可交换和关联的（我们一直依赖于这一点：否则“集合的按位或”的整个前提将是模棱两可的），按位或这样的集合等于其与范围 [ A , 2 n  - 1] 的交集及其与范围 [2 n , B ] 的交集的位或的位或。（例如，{7,8,9} 的按位或等于 7 和 9 的按位或，其中 7 是 {7} 的按位或，9 是 {8 的按位或， 9}.) 因此，使用案例#1 和案例#2 的结果，我们知道这样一个集合的按位或是[ A , 2 n中的任何元素的按位或− 1] 和来自 [2 n , 2 n  + 2 m +1 − 1  ] 的任何元素 ，其中m定义与案例 #2 相同。
    • 现在，这些按位或必须落在 [2 n  +  A , 2 n +1  - 1] 的范围内：
      • 它们不能小于 2 n  +  A因为它们必须在位置 n 处具有 a ，1并且在位置n的右侧，它们必须具有[ A , 2 n  - 1]中某个数字的所有位.1
      • 它们不能大于 2 n +1  - 1 因为这需要位置n1左侧的某个位置。
    • 相反，[2 n  +  A , 2 n +1 - 1] 范围内的每个值都是 2 n和 [ A , 2 n  - 1]范围内的数字 的按位或。
    • 因此，这些集合的所有不同按位或的集合是 [2 n  +  A , 2 n +1  - 1]。

因此，结合这三种情况，我们需要 [ A , 2 n  - 1], [2 n , 2 n  + 2 m +1  - 1] 和 [2 n  +  A , 2 n + 1  - 1]，其中（合并前两个）是 [ A , 2 n  + 2 m +1  - 1] 和 [2 n  +  A , 2 n +1  - 1] 的并集。请注意，这两个范围可能会重叠，但无论哪种方式都非常简单：如果范围重叠，则我们合并它们，否则我们不合并，范围 [ x，y ] 是y  -  x  + 1。

它们重叠的一个例子：如果A是0000_0101和B是1001_0011，那么我们需要 [ 0000_0101, 1001_1111] 和 [ 1000_0101, ] 的并集1111_1111，这意味着 [ 0000_0101, 1111_1111]，即 [5, 255]，它包含 251 个元素。

它们不重叠的一个例子：如果A是0001_0011和B是1000_0101，那么我们需要 [ 0001_0011, 1000_0111] 和 [ 1001_0011, ] 的并集1111_1111，即 [19, 135] 和 [147, 255]，其中包含 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≤  乙 < 2 9。不用说，do_it_fast比大B快得多；在我的机器上，一旦B达到 100,000 左右，即使是一次调用也需要相当长的时间。do_it_slowdo_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;
}

推荐阅读