Assume a RAM model has words of sufficient long. So a integer vector

*(x[0],x[1],…,x[n-1])*can be encoded as a word

*X=x[0]*2^0+x[1]*2^w+x[2]*2^(2w)+…*, here w is called width and satisfies

*2^w>x[i]*. The powerful bitwise trick is to change the width freely in O(1) time. Say we want to change the width of X from w to w’. Let

*temp_w=max(w,w’) * (n+1)*. We first enlarge the width of

*X*to

*temp_w*by letting

*X=X*2^0+ X*2^(temp_w-w)+X*2^(2*(temp_w-w))+…*and masking out the unwanted bits of X. Then we narrow the width of X to w’ by letting

*X=X%(2^(temp_w-w’)-1)*, which works due to

*temp_w>=n*w’*.

A good application of the above trick is to count the number of ‘1’s in the binary representation of a integer in O(1) time. Assume the integer X has n bits and let *2^m>n* and *2^(m-1)<=n*. We consider n as an encoded vector of width 1 and length n and change the width of *X* to m and *X%(2^m-1)* is just the answer. The above method need that a word on the RAM has at least *(n-1)(n+1)m+1* bits due to the large intermediate *temp_w.*

In fact the needed word bits can be further reduced to *(n-1)m+1, *where* m**=ceil(log n), * for this problem. Assume *m *and n are relatively prime, otherwise we can do some preprocessing to assure it. Let *X’=X*2^0+X*2^n+…+X*2^(n*(m-1)), *which is a concatenation of m copies of original X. Then we pick the 0-th, m-th , 2m-th, …, and (n-1)*m-th bits of X’ by masking out other bits. Then the answer is *X’%(2^m-1)*. The fact gcd(m,n)=1 leads to that the 0-th, m-th ,…,(n-1)*m-th bits of *X’* contains exactly the original bits of X, although not in the original order.