Thread Subject: count number of "on" bits?

How would I do a bitcount in matlab?

For example, say I have the unsigned 8 bit integer 170, which is '10101010'. Is there a function to count that it has 4 "on" (1) bits?

Thanks.

d=17465765
[crap,e]=log2(max(d));
n=sum(rem(floor(d*pow2(1-max(1,e):0)),2));

> d=17465765
> [crap,e]=log2(max(d));
> n=sum(rem(floor(d*pow2(1-max(1,e):0)),2));

How in the world you can come up with that, I'll never know. But thanks! :)

You can use length and find fucntions to solve your problem.

> d=17465765
> [crap,e]=log2(max(d));
> n=sum(rem(floor(d*pow2(1-max(1,e):0)),2));

quick question.

Why the max(d) in the log2 statement? Isn't max(number) always just the number?

I took the max(d) out and it still seems to count ok. Was there a good reason for it?

Thanks.

On Jul 30, 5:57=A0am, bogfrog <jmcg...@rcn.com> wrote:
> How would I do a bitcount in matlab?
>
> For example, say I have the unsigned 8 bit integer 170, which is '1010101=
0'. =A0Is there a function to count that it has 4 "on" (1) bits?
>
> Thanks.

>>help bitget

bogfrog <jmcgraw@rcn.com> wrote in message
<3817980.1217390262927.JavaMail.jakarta@nitrogen.mathforum.o
rg>...
> How would I do a bitcount in matlab?
>
> For example, say I have the unsigned 8 bit integer 170,
which is '10101010'. Is there a function to count that it
has 4 "on" (1) bits?
>
> Thanks.

>> sum(dec2bin(170)-'0')

ans =

     4

bogfrog:
<SNIP counting bits...

one of the solutions

     n=170;
     r=sum(bitget(n,1:8));
% r = 4

us

bogfrog <jmcgraw@rcn.com> wrote in message
<2156845.1217398241891.JavaMail.jakarta@nitrogen.mathforum.org>...
> > d=17465765
> > [crap,e]=log2(max(d));
> > n=sum(rem(floor(d*pow2(1-max(1,e):0)),2));
>
> quick question.
>
> Why the max(d) in the log2 statement? Isn't max(number)
always just the number?
>
> I took the max(d) out and it still seems to count ok. Was
there a good reason for it?
>
> Thanks.


Seems like there's no shortage of solutions here, but for
the record i was lazy and just copied that line out of
dec2bin. I believe the max(d) is there for cases where d is
a vector, so it uses e of the largest d.

If you're doing this many times in a loop you should try of
the solutions here and see which one is fastest. I had come
up with an alternate method of

s=sum(dec2bin(d)=='1') but on my computer the method i
posted above is about twice as fast.

> If you're doing this many times in a loop you should
> try of
> the solutions here and see which one is fastest. I
> had come
> up with an alternate method of
>
> s=sum(dec2bin(d)=='1') but on my computer the method
> i
> posted above is about twice as fast.

I ended up writing it in C and using a mex file. Everything in matlab was just too slow.

Thanks, though.

bogfrog <jmcgraw@rcn.com> wrote in message
<2748437.1217439315576.JavaMail.jakarta@nitrogen.mathforum.o
rg>...
> > If you're doing this many times in a loop you should
> > try of
> > the solutions here and see which one is fastest. I
> > had come
> > up with an alternate method of
> >
> > s=sum(dec2bin(d)=='1') but on my computer the method
> > i
> > posted above is about twice as fast.
>
> I ended up writing it in C and using a mex file.
Everything in matlab was just too slow.
>
> Thanks, though.

Gonna share??

> Gonna share??


Sure. But it's optimized for a sparse number of 1's. It's just based on some c-code I found online. It's still not as fast as I'd _really_ like, but here is the source:

---------------------------------
#include "mex.h"

void mexFunction(int nlhs, mxArray *plhs[],
int nrhs, const mxArray *prhs[]) {
    
    unsigned int n, c;
    
/* check: only one input and one output argument */
    if (nrhs !=1)
        mexErrMsgTxt("Must have one input argument");
    if (nlhs !=1)
        mexErrMsgTxt("Must have one output argument");
    
    n = mxGetScalar(prhs[0]);
    
    c = 0;
    while (n) {
        c++ ;
        n &= (n - 1) ;
    }
    plhs[0]=mxCreateDoubleMatrix(1,1,mxREAL);
    *mxGetPr(plhs[0])=c;
}
--------------------------------------

If you name it bitcount_c.c, just do "mex bitcount_c.c" at the command line and use it as so:

numbits = bitcount_c(number)

> Gonna share??

Oh, and if you are interested, here is the link with a bunch of different c code bitcount functions:

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

You can modify the matlab .c file I posted with any of those.

I prefer the following (which I didn't spot):

int bitcount(unsigned n) {
  n = ((n >> 1) & 0x55555555) + (n & 0x55555555);
  n = ((n >> 2) & 0x33333333) + (n & 0x33333333);
  n = ((n >> 4) & 0x0f0f0f0f) + (n & 0x0f0f0f0f);
  n += n >> 8;
  n += n >> 16;
  return n & 0xff;
}

The following times are those to count the bits in all 4 billion 32-bit integers on 64-bit ubuntu linux.
 
With a fast multiply, the following can be significantly faster than my previous post (25s v 32s):

int bitcount(unsigned n) {
  n -= (n >> 1) & 0x55555555;
  n = ((n >> 2) & 0x33333333) + (n & 0x33333333);
  return (((n + (n >> 4)) & 0x0f0f0f0f) * 0x01010101) >> 24;
}

see page 180 of
http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF

However, if you are counting bits of lots of integers at once, the look-up method can be even faster (once the look-up table is loaded into cache - 19s)

int count(unsigned v) {
  static const int BitsSetTable256[] =
  { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
  , 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5
  , 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5
  , 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
  , 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5
  , 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
  , 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
  , 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7
  , 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5
  , 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
  , 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
  , 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7
  , 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
  , 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7
  , 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7
  , 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
  };

  return BitsSetTable256[v & 0xff] +
    BitsSetTable256[(v >> 8) & 0xff] +
    BitsSetTable256[(v >> 16) & 0xff] +
    BitsSetTable256[v >> 24];
}

This is a modified version of a routine in http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

I changed the table from (unsigned char) to (int) as it is faster to add directly from the table than to convert unsigned char to int before adding.

If the routine is inlined, the time drops to 15s. With a bit of assembler hacking, the time can drop below 12s.