Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
count number of "on" bits?

Subject: count number of "on" bits?

From: bogfrog

Date: 30 Jul, 2008 03:57:12

Message: 1 of 16

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.

Subject: count number of

From: matt dash

Date: 30 Jul, 2008 04:22:01

Message: 2 of 16

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

Subject: count number of

From: bogfrog

Date: 30 Jul, 2008 04:52:57

Message: 3 of 16

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

Subject: count number of "on" bits?

From: Yumnam Kirani Singh

Date: 30 Jul, 2008 04:56:13

Message: 4 of 16

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

Subject: count number of

From: bogfrog

Date: 30 Jul, 2008 06:10:11

Message: 5 of 16

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

Subject: count number of "on" bits?

From: Igor

Date: 30 Jul, 2008 09:05:26

Message: 6 of 16

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

Subject: count number of

From: Steve Amphlett

Date: 30 Jul, 2008 09:30:05

Message: 7 of 16

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

Subject: count number of

From: us

Date: 30 Jul, 2008 09:38:02

Message: 8 of 16

bogfrog:
<SNIP counting bits...

one of the solutions

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

us

Subject: count number of

From: matt dash

Date: 30 Jul, 2008 14:26:01

Message: 9 of 16

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.

Subject: count number of

From: bogfrog

Date: 30 Jul, 2008 17:34:44

Message: 10 of 16

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

Subject: count number of

From: Steve Amphlett

Date: 30 Jul, 2008 17:50:18

Message: 11 of 16

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

Subject: count number of

From: bogfrog

Date: 30 Jul, 2008 18:36:50

Message: 12 of 16

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

Subject: count number of

From: bogfrog

Date: 30 Jul, 2008 18:41:37

Message: 13 of 16

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

Subject: count number of

From: Andy Robb

Date: 3 Aug, 2008 11:32:28

Message: 14 of 16

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

Subject: count number of

From: Andy Robb

Date: 14 Sep, 2008 19:51:02

Message: 15 of 16

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.

Subject: count number of "on" bits?

From: Oliver Woodford

Date: 22 Nov, 2013 15:20:15

Message: 16 of 16

bogfrog wrote:
> 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?

An optimized mex file, using the popcount instruction where available (on newer x86 architectures), or a lookup table for byte chunks where not, will probably be the fastest solution. But if you're happy with a reasonably fast, pure MATLAB implementation then I have made one available on the FEX here:
http://www.mathworks.com/matlabcentral/fileexchange/44371

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us