C - Bit operation without loop

Question

I am trying to calculate a value in function of bits in a word of variable length. Starting MSB, if bit is 1 then the value is 1/2^i. This value is multiplied by a scaling factor

Example: 110010 this would be (1/2 + 1/4 + 1/64) * scaling_factor

I have programmed it with a for loop; any idea of how this could be done avoiding the loop?

This is the code:

double dec_bnr (unsigned long data, int significant_bits, double scaling_factor)
{
    unsigned int temp;
    unsigned int bnr_locmask = 0x8000000;
    temp = data & bnr_locmasks[significant_bits-1];
    double result = 0;

    for (int i=0; i<significant_bits; i++){
        if((temp & bnr_locmask)==bnr_locmask){
            result+=pow (0.5, i+1);
        }
        bnr_locmask = bnr_locmask >> 1;
    }
    return result * scaling_factor;
}

Thank you in advance!

Edit: Thank you for your answers; however, what I am trying to say is not what you propose. Please, let me add an example: data=a0280

A       2   4   8   16  32  64  128 256 512 1024    2048    4096    8192
1/A     0,5     0,125                               0,000488281     0,00012207
data    1   0   1   0   0   0   0   0   0   0        1        0         1   0000000

result = scaling_factor*Sum(data/A)

We only take into account the value 1/A if the bit for that position is 1.

It's a mask to leave only significant bits starting from MSB — user3062084
– user3062084, Commented Aug 3, 2014 at 9:34
Following the edit... data = 0xA0280 represents (1/(2^1) + 1/(2^3) + 1/(2^11) + 1/(2^13)), yes ? If we multiply that by (2^20) we get (2^19 + 2^17 + 2^9 + 2^7), which is the integer 0xA0280... ldexp((double)data, -20) floats the integer 0xA0280 and then divides by (2^20)... it's not clear to me what the various respondents are missing :-( — user3793679
– user3793679, Commented Aug 3, 2014 at 10:25

Edward · Accepted Answer · 2014-08-03 15:41:47Z

3

It's actually very easy to do without a loop:

double dec_bnr (unsigned long data, double scaling_factor)
{
    return data*scaling_factor/(ULONG_MAX+1.0);
}

It's worth noting what happens in this code. First, data is converted into a double to match scaling_factor and then the numbers are multiplied, but then we do a further scaling dividing by ULONG_MAX+1.0 which is also converted to a double before dividing. Note that

This can't be ULONG_MAX + 1 because that would cause the number to remain an integer type and wrap around to zero (and thus causing a divide-by-zero error at runtime).
The number ULONG_MAX + 1.0, interpreted as a double, may well be identical to ULONG_MAX on 64-bit machines

It's called fixed point arithmetic and there are many resources available on the internet and elsewhere that explain it very well.

edited Aug 3, 2014 at 15:41

answered Aug 2, 2014 at 17:00

Edward

7,1402 gold badges31 silver badges60 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

chux Over a year ago

ULONG_MAX is at least 4,294,967,295. Better to use data*scaling_factor/(ULONG_MAX+1.0). There is little or nothing gained in omitting + 1.

Edward Over a year ago

@chux: Have you tried it? I have. In fact, using gcc 4.8.3-1 with optimization flag -O2 here, it generates exactly the same code either way. There is literally nothing to be gained in including it.

chux Over a year ago

Yes.

double dec_bnr (unsigned long data, double scaling_factor) { return data*scaling_factor/ULONG_MAX; } double dec_bnr1(unsigned long data, double scaling_factor) { return data*scaling_factor/(ULONG_MAX+1.0);} printf("%.20e\n", dec_bnr(1, 1.0)); printf("%.20e\n", dec_bnr1(1, 1.0));

--> "2.32830643708079737531e-10" and "2.32830643653869628906e-10" which are different answers.

user3793679 Over a year ago

Indeed... dividing by 0xFF...FF is almost bound to generate rounding, where dividing by 0x100...00 definitely won't.

user3793679 Over a year ago

...unless the 0xFF...FF when it is floated rounds to 0x100..00 ! (As in (double)UINT64_MAX, for your usual 64-bit double.)

|

score 2 · Accepted Answer · 2014-08-03 17:12:33Z

2

Or you could use ldexp():

  double result = ldexp(data * scaling_factor, -significant_bits) ;

which has the advantage of expressing exactly what you are doing ! (Assuming that the scaling_factor is double.)

It also avoids any issues with constructing large powers of two ((double)(ULONG_MAX + 1) doesn't quite work !) and dividing, or doing pow(2.0, -significant_bits) and multiplying.

Further thought... this is, of course, equivalent:

  double result = ldexp((double)data, -significant_bits) * scaling_factor ;

But you could lump the "binary point shift" in with the scaling_factor (once):

  double scaling_factor_x = ldexp(scaling_factor, -significant_bits) ;

and then the conversion is simply:

  double result = (double)data * scaling_factor_x ;

edited Aug 3, 2014 at 17:12

answered Aug 2, 2014 at 20:08

user3793679

Comments

David Grayson · Accepted Answer · 2014-08-02 16:59:12Z

0

This, or something similar, should be equivalent to what you are doing:

(double)data / 0x100000000 * scaling_factor

The way binary works is that each bit has a weight twice the weight of the bit after it, so you don't need to loop through the bits like you are doing.

answered Aug 2, 2014 at 16:59

David Grayson

88.1k24 gold badges159 silver badges195 bronze badges

Collectives™ on Stack Overflow

C - Bit operation without loop

3 Answers 3

11 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

11 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related