how many distinct numbers can be generated by doing bitwise OR of one or more integers between A and B (inclusive)

Question

How many distinct numbers can be generated by doing bitwise OR of one or more integers between A and B (inclusive)?

Explanation: In this case, A=7 and B=9. There are four integers that can be generated doing the bitwise OR of a non-empty subset of {7, 8, 9}: 7, 8, 9 and 15 1≤A≤B<2^60

My approach: Converted both the given numbers to binary. Iterated through them and tried to form different conditions. But I am not getting numbers of distinct integers. Please help me out how to develop the algorithm and program for this.

Answer 1

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.)

Now, any set of values in the range [A, B] falls into one of three cases:

• 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].

So, combining the three cases, we need the union of [A, 2ⁿ − 1], [2ⁿ, 2ⁿ + 2^m+1 − 1], and [2ⁿ + A, 2ⁿ⁺¹ − 1], which (merging the first two) is the union of [A, 2ⁿ + 2^m+1 − 1] and [2ⁿ + A, 2ⁿ⁺¹ − 1]. Note that those two ranges may overlap, but either way it's pretty simple: if the ranges overlap then we merge them, if not we don't, and the number of elements in a range [x, y] is 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.

---

Below is an implementation of this approach in C. (It should be straightforward to port it to any vaguely C-like language, such as C++, Java, C#, JavaScript, or 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;
  }
}

As you can see, the implementation itself is much shorter than all the argumentation that went into determining that it gives the right result.

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, even a single call to do_it_slow takes a noticeable amount of time once B gets up to 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;
}

Answer 2

I have tried a bit naive approach to this problem in which I create a set and then iterate through numbers from A to B and then bitwise Or them and put the value in the set.

Since,set has only distinct values ,therefore the length of set becomes the solution but the time complexity is O(n^2).

Looking for some bit manipulation technique to reduce the time complexity.