Pelles C forum
C language => Work in progress => Topic started by: Deth 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.
Thanx in advance.

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 "latexlike" math expression for this is (supposing n=maximum length of the sequence, 8 in the example):
\sum_{i=1}^{n2} i(i+1)/2
That is the sum of the first n2 triangular numbers.

Oh, by the way, if you expand the final expression you have something like (k=n2):
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

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

Why not a loop? Since noone 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.

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

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