Posted on: 12 Cresco 0:3 - 19.55.12
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
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.
User Comments: 8
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?
The algorithm I found is O(1)
Is a generating formula (it gives a value for each place) ok? I don't see any other way of generating those values.
Best I've found is O(log n).
I'm going to assume we can post solutions, or at least half-solutions.
def num(a, b, place):
if b<1: return 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)).
You're correct, when I said O(1) I was talking on a per bit basis.
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):
if (M >> power == N >> power):
if (N & ((1 << power+1) - 1) < 1 << power):
return N - M + 1
if (N & ((1 << power+1) - 1) >= 1 << power):
return N - (getNextLower(N,power+1) + (1 << power)) + 1
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):
if (M << power + 1 == N << power+1):
if (__name__ == "__main__"):
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)
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.
You must be logged in to add a comment