Step by Step solution about How to resolve the algorithm Population count step by step in the C programming language

This C code explores the following topics:

• Bit Counting Functions: It uses __builtin_popcountll and bitcount64 to count the number of set bits (1s) in a binary number.

• Evil and Odious Numbers: It generates "evil" and "odious" numbers, which have certain properties related to the count of set bits in their binary representations.

A detailed explanation of the code:

#include <stdio.h>

• Includes the standard input-output library.

int main() {
 // ...
}

• Defines the main function, which is the entry point of the program.

{
 unsigned long long n = 1;
 for (int i = 0; i < 30; i++) {
   printf("%d ", __builtin_popcountll(n));
   n *= 3;
 }
 printf("\n");
}

• This block demonstrates the use of __builtin_popcountll to count the set bits in a series of numbers. It starts with n=1 and multiplies it by 3 for each iteration. It prints the number of set bits in each iteration.

int od[30];
int ne = 0, no = 0;
printf("evil  : ");
for (int n = 0; ne+no < 60; n++) {
 if ((__builtin_popcount(n) & 1) == 0) {
   if (ne < 30) {
     printf("%d ", n);
     ne++;
   }
 } else {
   if (no < 30) {
     od[no++] = n;
   }
 }
}
printf("\n");
printf("odious: ");
for (int i = 0; i < 30; i++) {
 printf("%d ", od[i]);
}
printf("\n");

• This block generates and prints "evil" and "odious" numbers.
  • "Evil" numbers have an even number of set bits.
  • "Odious" numbers have an odd number of set bits.
  • The code uses __builtin_popcount to check the number of set bits and stores them in ne for evil numbers and no for odious numbers.
  • It then prints the first 30 "evil" numbers and the first 30 "odious" numbers.

#if defined(__POPCNT__) && defined(__GNUC__) && (__GNUC__> 4 || (__GNUC__== 4 && __GNUC_MINOR__> 1))
#define HAVE_BUILTIN_POPCOUNTLL
#endif
static uint64_t bitcount64(uint64_t b) {
 b -= (b >> 1) & 0x5555555555555555;
 b = (b & 0x3333333333333333) + ((b >> 2) & 0x3333333333333333);
 b = (b + (b >> 4)) & 0x0f0f0f0f0f0f0f0f;
 return (b * 0x0101010101010101) >> 56;
}
/* For 32-bit, an 8-bit table may or may not be a little faster */
static uint32_t bitcount32(uint32_t b) {
 b -= (b >> 1) & 0x55555555;
 b = (b & 0x33333333) + ((b >> 2) & 0x33333333);
 b = (b + (b >> 4)) & 0x0f0f0f0f;
 return (b * 0x01010101) >> 24;
}

• These functions provide alternative ways to compute the number of set bits. They use bit manipulation techniques to optimize the count. They are not directly used in this program but are provided as additional examples.

#include <stdio.h>

int main() {
  {
    unsigned long long n = 1;
    for (int i = 0; i < 30; i++) {
      // __builtin_popcount() for unsigned int
      // __builtin_popcountl() for unsigned long
      // __builtin_popcountll() for unsigned long long
      printf("%d ", __builtin_popcountll(n));
      n *= 3;
    }
    printf("\n");
  }

  int od[30];
  int ne = 0, no = 0;
  printf("evil  : ");
  for (int n = 0; ne+no < 60; n++) {
    if ((__builtin_popcount(n) & 1) == 0) {
      if (ne < 30) {
	printf("%d ", n);
	ne++;
      }
    } else {
      if (no < 30) {
	od[no++] = n;
      }
    }
  }
  printf("\n");
  printf("odious: ");
  for (int i = 0; i < 30; i++) {
    printf("%d ", od[i]);
  }
  printf("\n");

  return 0;
}


#if defined(__POPCNT__) && defined(__GNUC__) && (__GNUC__> 4 || (__GNUC__== 4 && __GNUC_MINOR__> 1))
#define HAVE_BUILTIN_POPCOUNTLL
#endif
static uint64_t bitcount64(uint64_t b) {
  b -= (b >> 1) & 0x5555555555555555;
  b = (b & 0x3333333333333333) + ((b >> 2) & 0x3333333333333333);
  b = (b + (b >> 4)) & 0x0f0f0f0f0f0f0f0f;
  return (b * 0x0101010101010101) >> 56;
}
/* For 32-bit, an 8-bit table may or may not be a little faster */
static uint32_t bitcount32(uint32_t b) {
  b -= (b >> 1) & 0x55555555;
  b = (b & 0x33333333) + ((b >> 2) & 0x33333333);
  b = (b + (b >> 4)) & 0x0f0f0f0f;
  return (b * 0x01010101) >> 24;
}