通过对 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。

\n\n

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

\n\n

由于我们忽略了第一个位置左侧的所有不同位置，因此我们假设这些位置中的位都是0。这样我们就得到了A  < 2 ⁿ  \xe2\x89\xa4  B，其中n是该位的位置。（例如，7 < 2 ³  \xe2\x89\xa4 9。）

\n\n

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

\n\n

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

\n\n

因此，结合这三种情况，我们需要 [ A , 2 ⁿ  \xe2\x88\x92 1]、[2 ⁿ , 2 ⁿ  + 2 ^{m +1}  \xe2\x88\x92 1] 和 [2 ⁿ  +  A , 2 ^{n +1}  \xe2\x88\x92 1]，（合并前两个）是 [ A , 2 ⁿ  + 2 ^{m +1}  \xe2\x88\x92 1] 和 [2 ⁿ  +  A , 2 ^{n +1}  \xe2\x88\x92 1]。请注意，这两个范围可能重叠，但无论哪种方式都非常简单：如果范围重叠，则我们将它们合并，如果不重叠，则不合并，并且范围 [ x , y ]中的元素数量为y  \xe2\x88\x92  x  + 1。

\n\n

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

\n\n

它们不重叠的例子：如果A是0001_0011且B是，那么我们需要 [ , ] 和 [ , ]1000_0101的并集，即 [19, 135] 和 [147, 255]，其中包含 117 和 108 个元素，分别为总共 225 个元素。0001_00111000_01111001_00111111_1111

\n\n\n\n

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

\n\n

int find_leftmost_differing_bit(uint64_t const A, uint64_t const B) {\n  int shift = 0;\n  while ((A >> shift) != (B >> shift)) {\n    ++shift;\n  }\n  return shift - 1;\n}\n\nint find_leftmost_1bit_to_right_of(uint64_t const B, int const n) {\n  for (int m = n - 1; m >= 0; --m) {\n    if ((B >> m) % 2 == 1) {\n      return m;\n    }\n  }\n  return -1;\n}\n\nuint64_t do_it_fast(uint64_t const A, uint64_t const B) {\n  if (A == B) {\n    return 1;\n  }\n  int const n = find_leftmost_differing_bit(A, B);\n  int const m = find_leftmost_1bit_to_right_of(B, n);\n  uint64_t const shared_bits = ((A >> (n + 1)) << (n + 1));\n  uint64_t const case_1_lower_bound = A;\n  uint64_t const case_2_upper_bound =\n    shared_bits + (1 << n) + (1 << (m + 1)) - 1;\n  uint64_t const case_3_lower_bound = A + (1 << n);\n  uint64_t const case_3_upper_bound = shared_bits + (1 << (n + 1)) - 1;\n  if (case_2_upper_bound < case_3_lower_bound - 1) {\n    return (case_3_upper_bound - case_3_lower_bound + 1)\n         + (case_2_upper_bound - case_1_lower_bound + 1);\n  } else {\n    return case_3_upper_bound - case_1_lower_bound + 1;\n  }\n}\n

\n\n

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

\n\n

调用该函数是do_it_fast因为，作为健全性检查，我还编写了一个名为do_it_slow（如下）的版本，它直接构建该集合，并确认这两个函数对所有 0 \xe2\x89\xa4  A  \xe2\给出相同的结果x89\xa4  B  < 2 ⁹。不用说，比大Bdo_it_fast快得多；在我的机器上，一旦B达到 100,000 左右，即使是一次调用也会花费相当长的时间。do_it_slowdo_it_slow

\n\n

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

\n