Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Jun 26th, 2012  |  syntax: Python  |  size: 1.26 KB  |  hits: 23  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
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)
create a new version of this paste RAW Paste Data