通过对A和B（含）之间的一个或多个整数进行按位或运算，可以生成多少个不同的数字？
说明： 在这种情况下，A ＝ 7并且B ＝ 9。通过对{7、8、9}的非空子集进行按位或运算，可以生成四个整数：7、8、9和15 1≤A≤B<2 ^ 60
我的方法： 将给定的数字都转换为二进制。遍历它们并尝试形成不同的条件。但是我没有得到不同整数的数量。请帮我解决如何为此开发算法和程序。
通过对A和B（含）之间的一个或多个整数进行按位或运算，可以生成多少个不同的数字？
说明： 在这种情况下，A ＝ 7并且B ＝ 9。通过对{7、8、9}的非空子集进行按位或运算，可以生成四个整数：7、8、9和15 1≤A≤B<2 ^ 60
我的方法： 将给定的数字都转换为二进制。遍历它们并尝试形成不同的条件。但是我没有得到不同整数的数量。请帮我解决如何为此开发算法和程序。
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^{n} ≤ B, where n is that bit position. (For example, 7 < 2^{3} ≤ 9.)
现在，[A，B]范围内的任何值都属于以下三种情况之一：
0
for every one of its elements.
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.)1
for every one of its elements.
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^{n} is 1000_0000
, then m is 4 -slash- 2^{m} is 0001_0000
.)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^{n}, 2^{n} + 2^{m+1} − 1].1000_0000
and B is 1001_0011
, then 1001_0000
, 1000_1000
, 1000_0100
, 1000_0010
, and 1000_0001
are all between 2^{n} and B.) So this means that for any value in the range [2^{n}, 2^{n} + 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 1
s — one at position n, one at another position you need.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^{n} − 1].1
somewhere to the left of position n.因此，结合这三种情况，我们需要[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^{9}. 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;
}
我尝试过一种天真的方法来解决此问题，在该方法中，我创建了一个集合，然后从A到B遍历数字，然后按位或它们进行迭代并将值放入集合中。
由于set仅具有不同的值，因此set的长度成为解，但时间复杂度为O（n ^ 2）。
寻找某种位操作技术以减少时间复杂度。