Hamming Weight to find the sum of 1 bits in the range between A and B inclusive I am trying to find the sum of 1 bits in the range between A and B inclusive, 

where -2^31 &lt;= A &lt;= B &lt;= 2^31 - 1

Input Format:

The first line contains the number of test cases T (&lt;=1000). Each of the next T lines contains two integers A and B.

I have used Hamming Weight algorithm to solve this problem. Though I have used memoization version of Hammnig Weight algorithm, it runs out of time.

mf = [-1 for i in range(65536)]

def count_1s(x):
    """It counts the number of 1 bits in an given 32 bit integer"""
    if (x &gt; 65535):
        return count_1s(x&amp;0xFFFF) + count_1s(x&gt;&gt;16)
    elif (mf[x] != -1):
        return mf[x]
    else:
        count = 0
        while(x &gt; 0):
            x &amp;= (x-1)
            count += 1
        mf[x] = count
        return mf[x]


t = int(input())

for i in range(t):
    a = [int(number) for number in input().split()]
    count = 0

    for j in range(a[0], a[1]+1):
        if (j &lt; 0):
            count += 32 - count_1s(-j-1)
        else:
            count += count_1s(j)

    print(count)


So I am in a need of improving this algorithm. Are there any ways to improve this algorithm? or I should use some other algorithm to solve this problem?

Link for Input:

https://hr-testcases.s3.amazonaws.com/56/input02.txt?AWSAccessKeyId=AKIAINGOTNJCTGAUP7NA&amp;Expires=1416339544&amp;Signature=5bf736TpbPUWcQZ%2FbGijtBHbVeM%3D&amp;response-content-type=text%2Fplain

Required Output:

https://hr-testcases.s3.amazonaws.com/56/output02.txt?AWSAccessKeyId=AKIAINGOTNJCTGAUP7NA&amp;Expires=1416339722&amp;Signature=NUwWGdUVsvttRWx0janzsxncDtY%3D&amp;response-content-type=text%2Fplain
The basic idea is not to manually go over all numbers from $A$ to $B$. For example, suppose $A = 0$ and $B = 2^n-1$. The $k$th bit of a number in $\{0,\ldots,2^n-1\}$ is $1$ exactly half the time, so the total number of $1$s is $n2^{n-1}$. Similarly, if $A = x2^n$ and $B = x2^n + 2^n-1$ then the number of $1$s is $n2^{n-1} + 2^nH(x)$, where $H(x)$ is the Hamming weight of $x$. In the general case, you have to decompose the range $[A,B]$ into a small number of ranges of the form just described. You should be able to do this with at most $2n$ or so ranges, where $n$ is the length of $B$ in bits.