We won't tell anyone you're here.

## Problem of the Whenever #15

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

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.
Post by Deckmaster on 12 Cresco 0:4 - 15.34.21
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?
Post by OmnipotentEntity on 12 Cresco 0:4 - 17.60.93
The algorithm I found is O(1)
Post by beary605 on 12 Cresco 2:2 - 12.9.19
Is a generating formula (it gives a value for each place) ok? I don't see any other way of generating those values.
Post by DIAV on 12 Cresco 2:3 - 4.90.51
Best I've found is O(log n).
Post by beary605 on 12 Cresco 2:4 - 19.23.22
I'm going to assume we can post solutions, or at least half-solutions.
def num(a, b, place):
if b<1return 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)).
Post by OmnipotentEntity on 12 Cresco 2:5 - 6.37.87
You're correct, when I said O(1) I was talking on a per bit basis.
Post by OmnipotentEntity on 12 Cresco 3:1 - 19.17.64
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)
Post by Deckmaster on 12 Cresco 3:2 - 6.45.9
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