计算每个位在整数范围内设置的次数

Question

给定从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.

Answer 1

每个位级都有一个由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和N都是相同的数2^(power+1).在这种情况下,有几个子类:

   1. 二者M并N使得两者M和N=相同数量的整数时除以2^(power).在这种情况下,如果N < 2^(power) mod 2^(power+1)那么答案是0,否则答案是N-M+1
   2. 否则它们是不同的,在这种情况下,答案是N - (N/2^(power+1))*2^(power+1) + 2**(power)(整数除法)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.

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

更新:

python实现

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)