Counting the number of set bits in an integer?

Question

I'm trying to use the x*x-1 to check to see if the integer is a power of 2 and then count it.

long count_bits(long n) {
unsigned int c;
for c = 0:n
n = n * (n - 1);  %Determines if an integer is a power of two!
c=c+1;
end

disp(c);

found my answer here: Calculating Hamming weight efficiently in matlab

The question is probably how can I mix C and matlab code and have it working... — aka.nice, Jan 08 '13 at 19:05
What exactly is your question? Are you looking to see if a particular number is a power of two? Are you trying to mix Matlab and C code? Are you @aka.nice or @Supa? — slayton, Jan 08 '13 at 19:36
@slayton I'm not Supra, maybe I should have used quotes "how can I...". My comments is just an observation on proposed piece of code... Understood irony can be a good tool, but once explained it is falling to pieces. — aka.nice, Jan 09 '13 at 13:05

Shai · Accepted Answer · 2013-01-09T07:31:20.097

Use bitget:

% generate a random int number
>> n = uint32( randi( intmax('uint32'), 1, 1 ) )

n = 

   3771981510

>> count = sum(bitget(n,1:32))

count = 

   18

Alternatively, if you are concern with performance, you can use a lookup table (LUT) to count the bits:

Constructing a LUT for 8-bits ints (only 256 entries):

function lut = countBitsLUT()
for ii = 0:255
    lut(ii+1) = sum(bitget(uint8(ii),1:8));
end

You only need to construct the LUT once.

Once you have the LUT, you can count the number of bits using:

count = lut( bitand(n,255)+1 ) + ...      % how many set bits in first byte
        lut( bitand( bitshift(n,-8), 255 ) + 1 ) + ... % how many set bits in second byte
        lut( bitand( bitshift(n,-16), 255 ) + 1 ) + ... % how many set bits in third byte
        lut( bitand( bitshift(n,-24), 255 ) + 1 ); % how many set bits in fourth byte

I also did a small "benchmark":

lutCount = @( n ) lut( bitand(n,255)+1 ) + ...      % how many set bits in first byte
        lut( bitand( bitshift(n,-8), 255 ) + 1 ) + ... % how many set bits in second byte
        lut( bitand( bitshift(n,-16), 255 ) + 1 ) + ... % how many set bits in third byte
        lut( bitand( bitshift(n,-24), 255 ) + 1 ); % how many set bits in fourth byte

t = [ 0 0 ];
for ii=1:1000
    n = uint32( randi( intmax('uint32'), 1, 1 ) );
    tic;
    c1 = sum(bitget(n,1:32));
    t(1) = t(1) + toc;
    tic;
    c2 = lutCount( n );
    t(2) = t(2) + toc;
    assert( c1 == c2 );
end

And the run times are:

t = [0.0115    0.0053]

That is, LUT is ~twice as fast as sum of bitget.

Counting the number of set bits in an integer?

1 Answers1