在若干循环向后通过最高阶位

我具有接收的整数，并且返回一组，它由2的幂，和其等于输入值的一个函数：在若干循环向后通过最高阶位

def bin_set(n): 
    b = set() 
    while n: 
     hbit = 1 << n.bit_length()-1 
     b.add(hbit) 
     n -= hbit 
    return b

所以我计算将该数字的最高位添加到该集合中，但我应该将哪个值发送给循环的下一个迭代？我使用n = n-hbit是因为while的情况，它以某种方式起作用，但我确信这是一种错误的方法。

是否有不同的方式来做到这一点，也许有不同的循环，没有对数/位twiddling/bit_length（），或者这是唯一的方法吗？

来源

2014-12-03 cbq

该方法工作得很好;用减法删除n中检测到的位，直到删除所有位。结果，n.bit_length()结果也下降。

而是减法，可以使用XOR（该^运营商）来清除高位：

def bin_set(n): 
    b = set() 
    while n: 
     hbit = 1 << n.bit_length() - 1 
     b.add(hbit) 
     n ^= hbit 
    return b

一种不同的方法将右移高位，而不是改变n：

def bin_set(n): 
    b = set() 
    hbit = 1 << n.bit_length() - 1 
    while hbit: 
     if n & hbit: # the high bit is set 
      b.add(hbit) 
     hbit >>= 1 
    return b

但这实际上做了更多的测试！

您的版本只循环多次，因为在n中设置了位，但会计算每次迭代的位数，而上面的版本会循环n.bit_length()次。 int.bit_length()需要O（N）平均时间来计算位长度，所以你需要花费O（KN）时间从N位产生一组K值，移位高位需要O（N）时间。

这使我的版本更好渐近，但由于int.bit_length()方法确实在C中工作，减少了循环到每4位只是一个循环迭代它并不像听起来那么糟糕。您需要巨大的号码才能开始看到我的胜利。

来源

2014-12-03 13:43:08

谢谢，使用异或来解除位的想法在我看来并没有发生，我更喜欢它！我实际上测试了第二个循环，在我看来，总是至少有一个迭代涉及到，尽管我想不出一个好的最坏情况。 – cbq 2014-12-03 14:03:46

@cbq：最差情况：一个非常大的整数，所有的位都被设置。例如，“19342813113834066795298815”。 – 2014-12-03 15:40:37

您可以使用一种称为set comprehension的东西，这是一种非常简洁的方式来创建它们。

def bin_set(n): 
    return {1 << p for p in xrange(n.bit_length()-1, -1, -1) if n & 1 << p} 

print bin_set(0) # --> set([])   
print bin_set(10) # --> set([8, 2])  
print bin_set(12) # --> set([8, 4])  
print bin_set(15) # --> set([8, 1, 2, 4])

来源

2014-12-03 14:51:40 martineau

在若干循环向后通过最高阶位

回答

相关问题