Problem of the Whenever #15
Post by: OmnipotentEntity
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.
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
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.
User Comments: 8
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.
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)).
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)]
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)).
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)
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:
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.
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
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.
You must be logged in to add a comment