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

由 msed发布于 2020-05-24 06:11:28

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

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

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

2020-05-24 06:11:28

First, express the numbers in binary, zero-padding both to the same number of bits. For example, if A = 7 and B = 9, then this gives 0111 and 1001.

Next, iterate from the left (the most significant bit) until you find a position where the two numbers differ. Ignore all positions to the left of that. (They're irrelevant, because they have the same bits for all values in the range, so they will also have the same bits for bitwise-ORs of any values in the range.) If you don't find such a position, then A = B and the answer is 1. If you do find such a position, then A has a 0 in that position and B has a 1 in that position.

Since we're ignoring all positions to the left of the first one where they differ, let's just pretend that the bits in those positions are all 0. That leaves us with A < 2ⁿ ≤ B, where n is that bit position. (For example, 7 < 2³ ≤ 9.)

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

Case #1: It may consist solely of values in the range [A, 2ⁿ − 1], meaning that the bit at position n is 0 for every one of its elements.
- If you take the bitwise-OR of any set of values in [A, 2ⁿ − 1], you'll still get a value in [A, 2ⁿ − 1]: the bitwise-OR of a set of positive integers will never be less than the greatest of those integers, and the bitwise-OR of a set with no 1s at position n (or higher) will never have a 1 at position n (or higher). (If these facts don't seem obvious at first, I recommend trying out some values until you see why they are true.)
- Conversely, for every value in [A, 2ⁿ − 1], you can easily construct a set whose bitwise-OR is that value: specifically, you can just take the set containing that value as its sole element.
- So, the set of all distinct bitwise-ORs for these sets is [A, 2ⁿ − 1].
Case #2: It may consist solely of values in the range [2ⁿ, B], meaning that the bit at position n is 1 for every one of its elements.
- This case is slightly trickier. To solve it, find the first 1 bit in B that is to the right of position n. Call that position m. (For example, if B is 1001_0011 and n is 7 -slash- 2ⁿ is 1000_0000, then m is 4 -slash- 2^m is 0001_0000.)
- Now, for every value in this range, every bit to the left of position m is 0, except for the bit at position n, which is 1; so you can never construct a set whose bitwise-OR will be outside the range [2ⁿ, 2ⁿ + 2^m+1 − 1].
- Additionally, for every position k at or to the right of position m, 2ⁿ + 2^k is in the range [2ⁿ, B]. (For example, if 2ⁿ is 1000_0000 and B is 1001_0011, then 1001_0000, 1000_1000, 1000_0100, 1000_0010, and 1000_0001 are all between 2ⁿ and B.) So this means that for any value in the range [2ⁿ, 2ⁿ + 2^m+1 − 1] (which would be [1000_0000, 1001_1111] for the example), you can construct a set whose bitwise-OR is that value, just by choosing elements that each have two 1s — one at position n, one at another position you need.
- So, the set of all distinct bitwise-ORs for these sets is [2ⁿ, 2ⁿ + 2^m+1 − 1].
Case #3: It may consist of one or more values in the range [A, 2ⁿ − 1] and one or more values in the range [2ⁿ, B].
- This case might seem trickier, but since bitwise-OR is commutative and associative (which we've been relying on this whole time: otherwise the whole premise of "bitwise-OR of a set" would be ambiguous), the bitwise-OR of such a set is equal to the bitwise-OR of the bitwise-OR of its intersection with the range [A, 2ⁿ − 1] and that of its intersection with the range [2ⁿ, B]. (For example, the bitwise-OR of {7,8,9} is equal to the bitwise-OR of 7 and 9, where 7 is the bitwise-OR of {7} and 9 is the bitwise-OR of {8,9}.) So, using our results from case #1 and case #2, we know that the bitwise-OR of such a set is the bitwise-OR of any element from [A, 2ⁿ − 1] and any element from [2ⁿ, 2ⁿ + 2^m+1 − 1], where m is defined as in case #2.
- Now, these bitwise-ORs must fall in the range [2ⁿ + A, 2ⁿ⁺¹ − 1]:
  - They can't be less than 2ⁿ + A because they have to have a 1 at position n and, to the right of position n, they have to have all the 1 bits of some number in [A, 2ⁿ − 1].
  - They can't be greater than 2ⁿ⁺¹ − 1 because that would require a 1 somewhere to the left of position n.
- Conversely, every value in the range [2ⁿ + A, 2ⁿ⁺¹ − 1] is the bitwise-OR of 2ⁿ and a number in the range [A, 2ⁿ − 1].
- So, the set of all distinct bitwise-ORs for these sets is [2ⁿ + A, 2ⁿ⁺¹ − 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 + 1 。

An example where they overlap: if A is 0000_0101 and B is 1001_0011, then we need the union of [0000_0101, 1001_1111] and [1000_0101, 1111_1111], which means [0000_0101, 1111_1111], i.e. [5, 255], which contains 251 elements.

An example where they don't overlap: if A is 0001_0011 and B is 1000_0101, then we need the union of [0001_0011, 1000_0111] and [1001_0011, 1111_1111], i.e. [19, 135] and [147, 255], which contain 117 and 108 elements, respectively, for a total of 225 elements.

下面是在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;
  }
}

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

The function is called do_it_fast because, as a sanity-check, I also wrote a version called do_it_slow (below) that directly builds the set, and confirmed that the two functions give the same result for all 0 ≤ A ≤ B < 2⁹. Needless to say, do_it_fast is much faster than do_it_slow for large B; on my machine, the difference becomes noticeable when B is around 100,000.

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;
}

柯南

2020-05-24 06:11:28

我尝试过一种天真的方法来解决此问题，在该方法中，我创建了一个集合，然后从A到B遍历数字，然后按位或它们进行迭代并将值放入集合中。

由于set仅具有不同的值，因此set的长度成为解，但时间复杂度为O（n ^ 2）。

寻找某种位操作技术以减少时间复杂度。

msed

这家伙很懒，什么都没留下

积分
0
话题
0
评论
3130
注册排名
1812