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 の後に 1 が続くパターンがあり2^powerます。

したがって、次の 3 つのケースがあります。

  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ものです。この場合、答えは、それ以外の場合、答えはNMN2^(power)N < 2^(power) mod 2^(power+1)0N-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。

この回答に論理的なバグが含まれている場合は、お知らせください。複雑で、何かを少し台無しにしてしまった可能性があります。

アップデート：

パイソン実装

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 に答える