# Untitled

By: a guest on Jun 26th, 2012  |  syntax: Python  |  size: 1.26 KB  |  hits: 23  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. def case1(M, N):
2.   return (N - M + 1) // 2
3.
4. def case2(M, N, power):
5.   if (M > N):
6.     return 0
7.   if (M // 2**(power) == N // 2**(power)):
8.     if (N % 2**(power+1) < 2**(power)):
9.       return 0
10.     else:
11.       return N - M + 1
12.   else:
13.     if (N % 2**(power+1) >= 2**(power)):
14.       return N - (getNextLower(N,power+1) + 2**(power)) + 1
15.     else:
16.       return getNextHigher(M, power+1) - M
17.
18.
19. def case3(M, N, power):
20.   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)
21.
22. def getNextLower(M, power):
23.   return (M // 2**(power))*2**(power)
24.
25. def getNextHigher(M, power):
26.   return (M // 2**(power) + 1)*2**(power)
27.
28. def numSetBits(M, N, power):
29.   if (M % 2**(power+1) == 0 and N % 2**(power+1) == 2**(power+1)-1):
30.     return case1(M,N)
31.   if (M // 2**(power+1) == N // 2**(power+1)):
32.     return case2(M,N,power)
33.   else:
34.     return case3(M,N,power)
35.
36. if (__name__ == "__main__"):
37.   print numSetBits(0,10,0)
38.   print numSetBits(0,10,1)
39.   print numSetBits(0,10,2)
40.   print numSetBits(0,10,3)
41.   print numSetBits(0,10,4)
42.   print numSetBits(5,18,0)
43.   print numSetBits(5,18,1)
44.   print numSetBits(5,18,2)
45.   print numSetBits(5,18,3)
46.   print numSetBits(5,18,4)