I am trying to find the sum of 1 bits in the range between A and B inclusive,
where -2^31 <= A <= B <= 2^31 - 1
Input Format:
The first line contains the number of test cases T (<=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 > 65535): return count_1s(x&0xFFFF) + count_1s(x>>16) elif (mf[x] != -1): return mf[x] else: count = 0 while(x > 0): x &= (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 < 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:
Required Output:
Asked By : Venkatesh
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/33280
0 comments:
Post a Comment
Let us know your responses and feedback