7

给定从 M 到 N 的整数范围，其中 M 和 N 可能不是 2 的幂。有没有一种有效的方法来计算每个位被设置的次数？

例如范围 0 到 10

0   0000
1   0001
2   0010
3   0011
4   0100
5   0101
6   0110
7   0111
8   1000
9   1001
10  1010

我想计算每列中每个位设置的次数，在这种情况下为 3,4,5,5。

4

2 回答 2

7

每个位级别都有一个由2^power0 和2^power1 组成的模式。

所以分三种情况：

  1. 何时M和N是这样的M = 0 mod 2^(power+1)和N = 2^(power+1)-1 mod 2^(power+1)。在这种情况下，答案很简单(N-M+1) / 2

  2. 当整数除以 时，M 和 N = 相同的M数。在这种情况下，有几个子情况：N2^(power+1)

    1. 两者M和N都是这样，当整数除以 时，两者M和= 相同的数字。在这种情况下，如果那么答案是，否则答案是N2^(power)N < 2^(power) mod 2^(power+1)0N-M+1
    2. 否则它们是不同的，在这种情况下，答案是N - (N/2^(power+1))*2^(power+1) + 2**(power)（整数除法） if N > 2^(power) mod 2^(power+1)，否则答案是(M/2^(power+1))*2^(power+1) - 1 - M

  3. 最后一种情况是 M 和 N = 整数除以 时的不同数字2^(power+1)。在这种情况下，您可以结合 1 和 2 的技术。求 和 之间的数字M个数(M/(2^(power+1)) + 1)*(2^(power+1)) - 1。然后在(M/(2^(power+1)) + 1)*(2^(power+1))和之间(N/(2^(power+1)))*2^(power+1)-1。最后在(N/(2^(power+1)))*2^(power+1)和之间N。

如果这个答案有逻辑错误，请告诉我，它很复杂，我可能稍微搞砸了一些东西。

更新：

蟒蛇实现

def case1(M, N):
  return (N - M + 1) // 2

def case2(M, N, power):
  if (M > N):
    return 0
  if (M // 2**(power) == N // 2**(power)):
    if (N % 2**(power+1) < 2**(power)):
      return 0
    else:
      return N - M + 1
  else:
    if (N % 2**(power+1) >= 2**(power)):
      return N - (getNextLower(N,power+1) + 2**(power)) + 1
    else:
      return getNextHigher(M, power+1) - M


def case3(M, N, power):
  return case2(M, getNextHigher(M, power+1) - 1, power) + case1(getNextHigher(M, power+1), getNextLower(N, power+1)-1) + case2(getNextLower(N, power+1), N, power)

def getNextLower(M, power):
  return (M // 2**(power))*2**(power)

def getNextHigher(M, power):
  return (M // 2**(power) + 1)*2**(power)

def numSetBits(M, N, power):
  if (M % 2**(power+1) == 0 and N % 2**(power+1) == 2**(power+1)-1):
    return case1(M,N)
  if (M // 2**(power+1) == N // 2**(power+1)):
    return case2(M,N,power)
  else:
    return case3(M,N,power)

if (__name__ == "__main__"):
  print numSetBits(0,10,0)
  print numSetBits(0,10,1)
  print numSetBits(0,10,2)
  print numSetBits(0,10,3)
  print numSetBits(0,10,4)
  print numSetBits(5,18,0)
  print numSetBits(5,18,1)
  print numSetBits(5,18,2)
  print numSetBits(5,18,3)
  print numSetBits(5,18,4)
于 2012-06-25T03:24:31.933 回答
0

它可以保持简单 -

取 x1 = 0001（用于在最右列找到 1）、x2 = 0010、x3 = 0100 等等。

现在，在一个循环中 -

n1 = n2 = n3 = 0
for i=m to n:
    n1 = n1 + (i & x1)
    n2 = n2 + (i & x2)
    n3 = n3 + (i & x3)

其中 - ni = 第 i 列中 1 的数量（从右开始）

于 2012-06-25T08:08:20.310 回答