The Forum > Front Page Posts > Problem of the Whenever #15
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. |
![[avatar]](/uploads/avatars/2_793765824.gif)
![[avatar]](/uploads/avatars/21_793087726.jpeg)
![[avatar]](/uploads/avatars/7346_877560879.png)
![[avatar]](/uploads/avatars/3753_793701997.png)
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)). |
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) |
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. |
The Forum > Front Page Posts > Problem of the Whenever #15