Some bitwise problems..

[VolatileObject]

I have a short (16bits) storing true and false (1 and 0) in the lower 9 bits, and I want to be able to count the number of 1s (or 0).
Example: 0000000010111010 (answer would be 5 in this case, total # of 1s)

This is what I came up with(assuming n is the value and total is the amount of 1s):

int i = 0, total = 0;
while(i++ < 9)
total += 1 - ~((n >>> 1) | 0xFFFE);

Is there a better way to do it in O(1) instead of O(n)?

Thanks in advance.

[ahoodin]

This gentlemen has some pretty good algorithms to compute the number of 1-bits in O(log n) machine instructions for you on his site:

http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

http://infolab.stanford.edu/~manku/bitcount/bitcount.c

[Twey]

I don't believe there is an O(1) solution, but there is an O(number of ones) algorithm involving repeatedly eliminating the least significant bit:

short int oneBits(short int n) {
short int total;

if (!n) return 0;

for (total = 1; n ^= ((n - 1) ^ n) & n; ++total);

return total;
}

To break it down, it works like this:

let n = 010111010b
n - 1 = 010111001 // subtract 1 to change all the bits up to the bit we're interested in
(n - 1) ^ n = 000000011 // XOR it with the original value to get only the changed bits (those up to and including the interesting bit)
((n - 1) ^ n) & n = 0000000010 // AND that with the original value to set only the interesting bit
n ^ (((n - 1) ^ n) & n) = 010111000 // XOR that with the original value to flip the interesting bit
if the new value of n is 0, we have no more 1 bits left, so exit

Edit: ah! There's a simpler algorithm to do the same thing in the top link in the post above (by ahoodin). Silly that I didn't see that :) *learns*

[ahoodin]

This solution is still O(n). There is a for loop. The op was looking for something a little better.

[Twey]

Yes, but n is the number of one bits, not the total number of bits — a significant improvement.

[Peter_B]

I have a short (16bits) storing true and false (1 and 0) in the lower 9 bits, and I want to be able to count the number of 1s (or 0).
Example: 0000000010111010 (answer would be 5 in this case, total # of 1s)

This is what I came up with(assuming n is the value and total is the amount of 1s):

int i = 0, total = 0;
while(i++ < 9)
total += 1 - ~((n >>> 1) | 0xFFFE);

Is there a better way to do it in O(1) instead of O(n)?

Thanks in advance.

Well, as you are restricting the input bit string to a mazimum of 16 bits, then technically your solution is O(1). I.e. there is some constant k such that the running time of your solution is always <k.

In fact, for any algorithm where the possible inputs are restricted to a finite set, there is an O(1) solution. To see this, just run through all possible inputs, find the one which takes the maximum time (and call this time T_max). Then the algorithm run time will be bound by T_max for all possible inputs, making it O(T_max).