二进制数中有两个一

Question

有没有一种算法可以找到a和b之间的所有二进制数，其中恰好有两个1？例如：

a = 5
b = 10
find(a, b)

它会找到

5 = 00000101
6 = 00000110
9 = 00001001
10 = 00001010

Answer 1

这些数字的形式是

2^m + 2^n

与 m > n.

您可以通过 m、n.

上的详尽搜索找到它们

M= 1
while M < b:
    N= 1
    while M + N <= b:
        if a <= M + N:
            print M + N
        N+= N
    M+= M

这可能会略微优化以避免在 2^m < a 时进行搜索，但好处很小：复杂度为 O(log²b)，已经很小了。

Answer 2

迭代所有包含相同数量 1 位的位模式的位破解技巧如下所示

unsigned next_combination(unsigned x)
{
  unsigned u = x & -x;
  unsigned v = u + x;
  x = v + (((v ^ x) / u) >> 2);
  return x;
}

它按升序生成值。它采用前一个值并将其转换为具有相同数量的 1 位的下一个值。这意味着您只需要从大于或等于 a 的最小位组合开始并迭代，直到遇到大于 b.

的值

当然，这种形式只有当你的a和b在unsigned的范围内时才有效。

Binary number with two one insite it