如何在不转换为二进制的情况下检查汉明权重？

问题描述 投票：0回答：10

如何在不实际转换和计数的情况下获得数字的二进制表示形式中的“1”的数量？

例如

  def number_of_ones(n):
      # do something
      # I want to MAKE this FASTER (computationally less complex).
      c = 0
      while n:
        c += n%2
        n /= 2
      return c


>>> number_of_ones(5)
    2
>>> number_of_ones(4)
    1
python algorithm discrete-mathematics hammingweight
10个回答
12
投票

我不是Python程序员，但希望它足以让你跟随。

c = 0
while n:
    c += 1
    n &= n - 1

return c

虽然有点晦涩难懂，但它的主要优点是速度和简单性。 while 循环仅对 n 中设置为 1 的每个位迭代一次。

7
投票

你无法降低计算的复杂性。它将是 O(n) 的位数，或者，如 & 技巧的答案所示，O(n) 的位数设置为 1；但除非您使用的所有数字都是特殊情况，否则后者平均应为 n/2，因此这两个 O(n) 数字是相同的。

当然，查找表技巧实际上对计算复杂性没有任何作用；它只是用空间来支付时间，但没有改变基本的经济学，即你必须以某种方式检查每一位一次，并且没有办法解决这个问题。从逻辑上讲，如果不检查每个位，您就无法回答有关数字中的位的问题。 现在，我想我有点草率了，因为这些例子中的许多实际上都是 O(n^2)，因为在 Python 中你必须一次检查整个数字，所以使用 Python 长整数，比如 100字节， + 或 & 或 / 操作将至少查看每个字节一次，并且会一遍又一遍地发生，直到数字减少到零（在上面概述的方案中），因此这些实际上是 O (n^2) 次操作。我不确定 Python 是否会允许真正的 O(n) 解决方案。

无论如何：如果你真的问的是

计算

复杂性，这具体意味着大O分析，这就是你的答案。 :-)

5
投票

def number_of_ones(n): sum = 0 while n != 0: sum += lookup_table[n & 0xff] n >>= 8 return sum 

我相信这是空间和运行时间之间相当好的权衡。

5
投票

sum( [x&(1<<i)>0 for i in range(32)] ) 




      

      
      
      

      

        

          

            

              
3
投票

              
            

          

        

        
https://en.wikipedia.org/wiki/Hamming_weight
。
O(log(n)) 的解决方案，n 是位长


m1  = 0x5555555555555555 #binary: 0101...
m2  = 0x3333333333333333 #binary: 00110011..
m4  = 0x0f0f0f0f0f0f0f0f #binary:  4 zeros,  4 ones ...
m8  = 0x00ff00ff00ff00ff #binary:  8 zeros,  8 ones ...
m16 = 0x0000ffff0000ffff #binary: 16 zeros, 16 ones ...
m32 = 0x00000000ffffffff #binary: 32 zeros, 32 ones
h01 = 0x0101010101010101 #the sum of 256 to the power of 0,1,2,3...

def hammingWeight(x: int) -> int:
    x -= (x>>1)&m1
    x = (x&m2) + ((x>>2)&m2)
    x = (x+(x>>4))&m4
    return ((x*h01)>>56)&0x7f



而在python 3.10中，int类型将有一个bit_count()方法

    





      

      
      
      

      

        

          

            

              
1
投票

              
            

          

        

        
这个问题
了解具体方法），并使用类似 ctypes 之类的内容与 C 实现进行交互。
    




      

      
      
      

      

        

          

            

              
1
投票

              
            

          

        

        



def bitCount(int_no):

    c = 0
    while(int_no):
        int_no &= (int_no - 1)
        c += 1
    return c




这可能是一种古老而有效的方法......最初是用 C 实现的（Algo 有一个我不记得的名字）。它对我来说效果很好，希望对其他人也有用

    





      

      
      
      

      

        

          

            

              
0
投票

              
            

          

        

        
最先进的技术
。
这是一个时常出现的话题，现代 CPU 有一个人口计数算法。这对于计算某些通信应用中的
误码率
很有用。这是汉明权重，与汉明距离相关，scipy 有一个实现，但它适用于数组，而不适用于数字的二进制表示。对于固定大小的计算，例如numpy数组，我知道的最快的方法是方法这个答案，但是提到的答案，我称之为分而治之方法。在一般情况下，分而治之的复杂性是O(log(n))而不是
O(n)
。对于大多数情况，接受的答案确实很好，在 C 等语言中甚至更好，您可以简单地采用 
((*char)bits)[i]
，而不是移动数字。
这里我给出了分而治之方法的一般实现，其中根据输入数字的大小动态计算掩码。


def dq_number_of_ones(n):
  nb = 1
  while n >> nb:
    nb *= 2
  t = (1 << nb) - 1
  masks = []
  while nb > 1:
    nb //= 2
    t ^= t >> nb
    masks.append(t)
  
  t = n
  s = 1
  for tm in masks[::-1]:
    tm = masks.pop()
    t = ((tm & t) >> s) + ((tm >> s) & t)
    s *= 2
  return t



为了完成这里OP的方法和接受的查找表方法


def number_of_ones(n):
    # do something
    # I want to MAKE this FASTER (computationally less complex).
    c = 0
    while n:
      c += n%2
      n //= 2
    return c
lookup_table = [number_of_ones(i) for i in range(256)]
def lt_number_of_ones(n):
    sum = 0
    while n != 0:
        sum += lookup_table[n & 0xff]
        n >>= 8
    return sum



两者的实际比较


import time
import matplotlib.pyplot as plt
x = []
t1 = []
t2 = []
t3 = []
for i in range(3,8000,20):
  y = i**i
  if i < 1000:
    time.sleep(0.0001)
    t0 = time.time()
    w1 = number_of_ones(y)
    t1.append(time.time() - t0)
  else:
    t1.append(np.nan)
  time.sleep(0.0001)
  t0 = time.time()
  w2 = dq_number_of_ones(y)
  t2.append(time.time() - t0)
  time.sleep(0.0001)
  t0 = time.time()
  _ = lt_number_of_ones(y)
  t3.append(time.time() - t0)
  time.sleep(0.0001)
  
  x.append(i)

plt.figure(figsize=(12, 4))
plt.subplot(121)
plt.plot(x, t1)
plt.plot(x, t2)
plt.plot(x, t3)
plt.xlim([10,None])
plt.title('Linear scale')
plt.ylabel('time to count bits in $x^x$')
plt.subplot(122)
plt.loglog(x, t1)
plt.loglog(x, t2)
plt.loglog(x, t3)
plt.xlim([10,None])
plt.title('Log scale')
plt.legend(['direct counting', 'lookup table', 'divide and conquer'])




    




      

      
      
      

      

        

          

            

              
0
投票

              
            

          

        

        


这使用了短路和递归，当n大于0时，它切换到计算
1+p(n&(n-1))
，其中调用
p(n&(n-1))
，依此类推，当n为0时，它返回0。复杂度为O(n)，因为它运行二进制中存在 1 的次数。
示例：
p(9) = 1+p(8) = 1+1+p(0) = 1+1+0=2
    





      

      
      
      

      

        

          

            

              
0
投票

              
            

          

        

        


我最终得到的结果显然比原来的计算量更大。另一方面，它捕获位集的索引偏移量，因此我将整数累积到列表中。


from math import floor, log



def bitCount(int_no):


if not isinstance( int_no, int) or int_no < 0:
    return None

count = 0
while(int_no):
    int_no &= (int_no - 1)
    count += 1
    
return count



def 位集（int_no）：


if not isinstance( int_no, int) or int_no < 0:
    return None

bit_indexes = []
while(int_no):
    index = floor(log(int_no, 2))
    int_no &= (pow(2, index) - 1)
    bit_indexes.insert(0, index)

return bit_indexes



如果您采用 len(bitsSet(n))，则会得到相同的答案。走很远的路回家...

    



      

      
    

  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.