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

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 < 2n ≤ B, where n is that bit position. (For example, 7 < 23 ≤ 9.)

• Case #1: It may consist solely of values in the range [A, 2n − 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, 2n − 1], you'll still get a value in [A, 2n − 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 `1`s 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, 2n − 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, 2n − 1].
• Case #2: It may consist solely of values in the range [2n, 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- 2n is `1000_0000`, then m is 4 -slash- 2m 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 [2n, 2n + 2m+1 − 1].
• Additionally, for every position k at or to the right of position m, 2n + 2k is in the range [2n, B]. (For example, if 2n is `1000_0000` and B is `1001_0011`, then `1001_0000`, `1000_1000`, `1000_0100`, `1000_0010`, and `1000_0001` are all between 2n and B.) So this means that for any value in the range [2n, 2n + 2m+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 `1`s — one at position n, one at another position you need.
• So, the set of all distinct bitwise-ORs for these sets is [2n, 2n + 2m+1 − 1].
• Case #3: It may consist of one or more values in the range [A, 2n − 1] and one or more values in the range [2n, 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, 2n − 1] and that of its intersection with the range [2n, 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, 2n − 1] and any element from [2n, 2n + 2m+1 − 1], where m is defined as in case #2.
• Now, these bitwise-ORs must fall in the range [2n + A, 2n+1 − 1]:
• They can't be less than 2n + 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, 2n − 1].
• They can't be greater than 2n+1 − 1 because that would require a `1` somewhere to the left of position n.
• Conversely, every value in the range [2n + A, 2n+1 − 1] is the bitwise-OR of 2n and a number in the range [A, 2n − 1].
• So, the set of all distinct bitwise-ORs for these sets is [2n + A, 2n+1 − 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.

``````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 < 29. 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;
}
``````