CODEWITHSUNDEEP
ctypestype-conversion
Mark
Mark

Reputation: 6494

promoting integer to long or unsigned long

static uint32_t get_num(void);

uint32_t get_count(unsigned int mask)
{
  uint8_t i = 0;
  uint32_t count = 0;

  while (i < get_num())
  {
     if (mask & (1 << i++))
       count++;
  }

  return count;
}

In this code, what would be more safe (1L << i++) or (1UL << i++) ?

Upvotes: 0

Views: 138

Answers (2)

too honest for this site
too honest for this site

Reputation: 12263

If you just want to count the 1-bits in an uint and use gcc, you should have a look at the builtin functions (here: int __builtin_popcount (unsigned int x)). These can be expected to be highly optimized and even use special instructions of the CPU where available. (one could very wenn test for gcc).

However, not sure what get_num() would yield - it just seems not to depend on mask, so its output can be used to limit the result of popcount.

The following uses a loop and might be faster than a parallel-add tree on some architectures (one should profile both versions if timing is essential).

unsigned popcount(uint32_t value, unsigned width)
{
    unsigned cnt = 0;   // actual size intentionally by arch

    if ( width < 32 )
        value &= (1UL << width) - 1;  // limit to actual width

    for ( ; value ; value >>= 1 ) {
        cnt += value & 1U;    // avoids a branch
    }
    return cnt;
}

Note the width is passed to the function.

On architectures with < 32 bits (PIC, AVR, MSP430, etc.) specialized versions will gain much better results than a single version.

Upvotes: 0

John Bollinger
John Bollinger

Reputation: 181459

An unsigned operand is a bit safer because only then is the behavior of all the shifts defined when get_num() returns the number of bits in that operand's type. If unsigned long is wider than unsigned int then UL is slightly safer than just U, but only for accommodating get_num() results that aren't valid anyway.

Safer yet, however, is this:

uint32_t get_count(uint32_t mask)
{
  uint8_t num = get_num();

  if (num == 0) return 0;

  /* mask off the bits we don't want to count */
  mask &= ~((uint32_t) 0) >> ((num < 32) ? (32 - num) : 0);

  /* count the remaining 1 bits in mask, leaving the result in mask */
  mask = (mask & 0x55555555) + ((mask & 0xaaaaaaaa) >> 1);
  mask = (mask & 0x33333333) + ((mask & 0xcccccccc) >> 2);
  mask = (mask & 0x0f0f0f0f) + ((mask & 0xf0f0f0f0) >> 4);
  mask = (mask & 0x00ff00ff) + ((mask & 0xff00ff00) >> 8);
  mask = (mask & 0x0000ffff) + ((mask & 0xffff0000) >> 16);

  return mask;
}

Upvotes: 1

Related Questions