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

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

- 积分

**0** - 话题

**0** - 评论

**3130** - 注册排名

**1812**

First, express the numbers in binary, zero-padding both to the same number of bits. For example, if

A= 7 andB= 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=Band the answer is 1. If you do find such a position, thenAhas a`0`

in that position andBhas 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 withA< 2^{n}≤B, wherenis that bit position. (For example, 7 < 2^{3}≤ 9.)现在，[A，B]范围内的任何值都属于以下三种情况之一：

Case #1:It may consist solely of values in the range [A, 2^{n}− 1], meaning that the bit at positionnis`0`

for every one of its elements.A, 2^{n}− 1], you'll still get a value in [A, 2^{n}− 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 positionn(or higher) will never have a`1`

at positionn(or higher). (If these facts don't seem obvious at first, I recommend trying out some values until you see why they are true.)A, 2^{n}− 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.A, 2^{n}− 1].Case #2:It may consist solely of values in the range [2^{n},B], meaning that the bit at positionnis`1`

for every one of its elements.`1`

bit inBthat is to the right of positionn. Call that positionm. (For example, ifBis`1001_0011`

andnis 7 -slash- 2^{n}is`1000_0000`

, thenmis 4 -slash- 2^{m}is`0001_0000`

.)mis`0`

, except for the bit at positionn, 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].kat or to the right of positionm, 2^{n}+ 2^{k}is in the range [2^{n},B]. (For example, if 2^{n}is`1000_0000`

andBis`1001_0011`

, then`1001_0000`

,`1000_1000`

,`1000_0100`

,`1000_0010`

, and`1000_0001`

are all between 2^{n}andB.) 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 positionn, one at another position you need.^{n}, 2^{n}+ 2^{m+1}− 1].Case #3:It may consist of one or more values in the range [A, 2^{n}− 1]andone or more values in the range [2^{n},B].A, 2^{n}− 1] and that of its intersection with the range [2^{n},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^{n}− 1] and any element from [2^{n}, 2^{n}+ 2^{m+1}− 1], wheremis defined as in case #2.^{n}+A, 2^{n+1}− 1]:^{n}+Abecause they have to have a`1`

at positionnand, to the right of positionn, they have to have all the`1`

bits ofsomenumber in [A, 2^{n}− 1].^{n+1}− 1 because that would require a`1`

somewhere to the left of positionn.^{n}+A, 2^{n+1}− 1] is the bitwise-OR of 2^{n}and a number in the range [A, 2^{n}− 1].^{n}+A, 2^{n+1}− 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

Ais`0000_0101`

andBis`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

Ais`0001_0011`

andBis`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都应该很简单。）

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

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`

ismuchfaster than`do_it_slow`

for largeB; on my machine, the difference becomes noticeable whenBis around 100,000.我尝试过一种天真的方法来解决此问题，在该方法中，我创建了一个集合，然后从A到B遍历数字，然后按位或它们进行迭代并将值放入集合中。

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

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