Blake was here
The Forum > Front Page Posts > Problem of the Whenever #15
 OmnipotentEntity Administrator636 Posts12 Cresco 0:3 - 19.55.12536.585 days ago Given a range of integers from M to N, where M and N might not be a powers of 2. Is there an efficient way to count the number of times each bit is set? For example the range 0 to 10 0   0000 1   0001 2   0010 3   0011 4   0100 5   0101 6   0110 7   0111 8   1000 9   1001 10  1010 I'd like the counts for the number of time each bit is set in each column which would be 3,4,5,5 in this case. Solution is on stackoverflow under my username if you really must see. And it'll be posted next week. [Quote] [Link]
 For clarification, what exactly is the cutoff for "efficient"? An O(n*k) algorithm is trivial, which in some situations would be considered efficient, so are you looking for logarithmic? Constant? Something else entirely? [Quote] [Link]
 OmnipotentEntity Administrator636 Posts12 Cresco 0:4 - 17.60.93535.682 days ago The algorithm I found is O(1) [Quote] [Link]
 Is a generating formula (it gives a value for each place) ok? I don't see any other way of generating those values. [Quote] [Link]
 Best I've found is O(log n). [Quote] [Link]
 I'm going to assume we can post solutions, or at least half-solutions. def num(a, b, place):        if b<1: return 0        c=2**place        d=divmod(b, c*2)        e=c*d[0]+(d[1]-c+1)*(d[1]-c+1>0)        return e-num(0, a-1, place)count=lambda a,b:[num(a, b, x) for x in range(int(math.log(b))+1, -1, -1)] My code focuses around repeating sections of the state on one bit. Find the number of full sets of repeating sections (call this A), and the number of elements in the last, unfinished section (call this B). Return A*(num of 1s in a set)+B-(num of 0s in a set)+1. I have no idea how you can get this down to constant time. The generation of the list must be at least O(log2(N)). [Quote] [Link]
 OmnipotentEntity Administrator636 Posts12 Cresco 2:5 - 6.37.87523.244 days ago You're correct, when I said O(1) I was talking on a per bit basis. [Quote] [Link]
 OmnipotentEntity Administrator636 Posts12 Cresco 3:1 - 19.17.64520.604 days ago And here's my answer to this problem. def case1(M, N):   return (N - M + 1) >> 1  def case2(M, N, power):   if (M > N):     return 0   if (M >> power == N >> power):     if (N & ((1 << power+1) - 1) < 1 << power):       return 0     else:       return N - M + 1   else:     if (N & ((1 << power+1) - 1) >= 1 << power):       return N - (getNextLower(N,power+1) + (1 << 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 >> power << power def getNextHigher(M, power):   return (M >> power) + 1 << power def numSetBits(M, N, power):   if (M & ((1 << power+1) - 1) == 0 and N + 1 >> power + 1 != N >> power + 1):     return case1(M,N)   if (M << power + 1 == N << 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) [Quote] [Link]
 Deckmaster-239.5 Posts12 Cresco 3:2 - 6.45.9520.24 days ago Now that Omni's finally given his, here's mine: def numSetBits(start, end, power):    if start > end or 0 > start:        return -1 # Invalid     elif 0 != start:        start -= 1 # Align start     mask = 1 << power    tmp = mask - 1    t = ~(tmp + mask)    out = ((end & t) - (start & t)) >> 1    if end & mask:        out += 1 + (end & tmp)    if start & mask:        out -= 1 + (start & tmp)    return out It's only designed for positive start, end where start <= end, but could easily be modified to handle other scenarios, such as start > end, negatives, and so on. [Quote] [Link]
The Forum > Front Page Posts > Problem of the Whenever #15