MATLAB Central Newsreader - count number of "on" bits?

count number of "on" bits?

bogfrog — Wed, 30 Jul 2008 03:57:12 -0400

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.

Re: count number of

matt dash — Wed, 30 Jul 2008 04:22:01 -0400

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

Re: count number of

bogfrog — Wed, 30 Jul 2008 04:52:57 -0400

> 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! :)

Re: count number of "on" bits?

Yumnam Kirani Singh — Wed, 30 Jul 2008 04:56:13 -0400

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

Re: count number of

bogfrog — Wed, 30 Jul 2008 06:10:11 -0400

> 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.

Re: count number of "on" bits?

Igor — Wed, 30 Jul 2008 09:05:26 -0400

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

Re: count number of

Steve Amphlett — Wed, 30 Jul 2008 09:30:05 -0400

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

Re: count number of

us — Wed, 30 Jul 2008 09:38:02 -0400

bogfrog:
<SNIP counting bits...

one of the solutions

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

us

Re: count number of

matt dash — Wed, 30 Jul 2008 14:26:01 -0400

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.

Re: count number of

bogfrog — Wed, 30 Jul 2008 17:34:44 -0400

> 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.

Re: count number of

Steve Amphlett — Wed, 30 Jul 2008 17:50:18 -0400

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??

Re: count number of

bogfrog — Wed, 30 Jul 2008 18:36:50 -0400

> 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)

Re: count number of

bogfrog — Wed, 30 Jul 2008 18:41:37 -0400

> 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.

Re: count number of

Andy Robb — Sun, 03 Aug 2008 11:32:28 -0400

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;
}

Re: count number of

Andy Robb — Sun, 14 Sep 2008 19:51:02 -0400

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.