How to count bit occurences?!

[Deth]

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.
Thanx in advance.

   

[cane]

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

You can adapt this to your situation.

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.

[cane]

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

[cane]

uhm... maybe that solves only the particular case... I think I need to twiddle with multisets.

[severach]

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]

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]

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?