### Author Topic: How to count bit occurences?!  (Read 7099 times)

#### Deth

• Guest ##### How to count bit occurences?!
« on: April 28, 2007, 10:45:33 pm »
Hi All,
I really need to know if there is any algorithm/formula for counting how much times there are fixed number of
bits ON in byte or word. To say, how many times any 3 bits in number 125 are ON without looping, such as:

target=0;
for(int i=0;i<125;i++)
{
if(bits_on_count(i)==3)
target++;
}
return target;

I think there should be some mathematical expression for this case, but I failed to formulate it.

#### cane

• Guest ##### Re: How to count bit occurences?!
« Reply #1 on: April 29, 2007, 08:57:10 pm »
Oops, I've misunderstood your post at first. But now I have a solution:

Suppose you are working with 8 bits sequences and want to know the number of numbers with 3 bits on:

- fix the 8th bit to 1
- fix the 7th bit to 1
- you have 6 remaining varying positions

next step:

- fix the 8th bit to 1
- fix the 6th bit to 1
- you have 5 remainig varying positions

Go on until you fix the 8th, 2nd and 1st bit.

The total is: 6+5+4+3+2+1

Now you exclude the 8th bit and do the same work on 7 bits sequences:

You have 5+4+3+2+1

Go on:

4+3+2+1
3+2+1
2+1
1

Sum all

56

The "latex-like" math expression for this is (supposing n=maximum length of the sequence, 8 in the example):

\sum_{i=1}^{n-2} i(i+1)/2

That is the sum of the first n-2 triangular numbers.
« Last Edit: April 30, 2007, 11:54:42 am by cane »

#### cane

• Guest ##### Re: How to count bit occurences?!
« Reply #2 on: April 30, 2007, 12:06:59 pm »
Oh, by the way, if you expand the final expression you have something like (k=n-2):

1/2 (\sum_{i=1}^{k} i + \sum_{i=1}^{k} i^2) = 1/2 (k(k+1)/2 + \sum_{i=1}^{k} i^2)

The sum of the first k square integers is nasty to obtain and is this: k(k+1)(2k+1)/6

Then just do simple algebra and you get:

k(k+1)(k+2)/6
« Last Edit: April 30, 2007, 12:11:05 pm by cane »

#### cane

• Guest ##### Re: How to count bit occurences?!
« Reply #3 on: April 30, 2007, 03:20:15 pm »
uhm... maybe that solves only the particular case... I think I need to twiddle with multisets.

#### severach

• Guest ##### Re: How to count bit occurences?!
« Reply #4 on: May 01, 2007, 04:59:10 am »
Why not a loop? Since no-one has solved this problem I think you're going to be using a loop. Perhaps your current loop testing one bit at a time just isn't efficient enough. Perhaps all you need is a more efficient implementation using tables.

Pick a set number of bits for which the table size is acceptable, say 8 bits for a 256 character table. Write an algorithm that fills the table with the proper bit count of each number. For all bit widths greater than 8 you cut the number up into 8 bit pieces. A 32 bit number would only take 4 table lookups in an 8 bit table.

#### cane

• Guest ##### Re: How to count bit occurences?!
« Reply #5 on: May 01, 2007, 10:53:51 am »
I think this time I have it It's just the multinomial coefficient: http://en.wikipedia.org/wiki/Multinomial_theorem

E.g.: number of 8bits numbers with 3 bits on: 8!/(3!5!)

#### Jeffrey

• Guest ##### Re: How to count bit occurences?!
« Reply #6 on: September 07, 2007, 10:53:09 pm »
Am new here, and although this post is a bit old, I have decided to contribute a simple solution to this problem.

I know that this isn't the most optimized technique, considering that this is no way to directly address a bit on the Intel architecture, which uses byte addressing, so this isn't something that you would want to use if you needed fast or small code.

Solution -- Bit Fields

Code: [Select]
#include <stdio.h>#pragma(1)typedef struct _bits_t {unsigned bit0 : 1;unsigned bit1 : 1;unsigned bit2 : 1;unsigned bit3 : 1;unsigned bit4 : 1;unsigned bit5 : 1;unsigned bit6 : 1;unsigned bit7 : 1;} bits_t;#pragma()int main(int argc, char *argv[]){unsigned byte = 0xAE;bits_t *bits;bits = &byte;printf("%d%d%d%d %d%d%d%d", x->bit7, x->bit6, x->bit5, x->bit4, x->bit3, x->bit2, x->bit1, x->bit0);return 0;}
Doing it this way may have its obvious downsides, but it definitely makes bit checking/manipulation a hell of a lot easier.

So what do you all think?