Najpierw bez rekurencji:
#include <stdio.h>
#include <limits.h>
unsigned short count_0bits(int value) {
unsigned short zero_bits = 0;
for (unsigned short i = 0; i < CHAR_BIT * sizeof(int); ++i) {
if ((value & (1 << i)) == 0) {
++zero_bits;
}
}
return zero_bits;
}
int main(void) {
for (int i = 0; i < 255; ++i) {
printf("%d, num zero bits: %d\n", i, count_0bits(i));
}
return 0;
}
Teraz trochę można zmodyfikować kod bo w zasadzie jest obojętne czy liczysz od przodu czy od tyłu:
#include <stdio.h>
#include <limits.h>
unsigned short count_0bits(int value) {
unsigned short zero_bits = 0;
unsigned short bits_counter = CHAR_BIT * sizeof(int);
while(bits_counter--) {
zero_bits += (value & (1 << bits_counter)) ? 0: 1;
}
return zero_bits;
}
int main(void) {
for (int i = 0; i < 255; ++i) {
printf("%d, num zero bits: %d\n", i, count_0bits(i));
}
return 0;
}
Teraz przekształcenie na wersję rekurencyjną. Wyciągam zmienną ilości zer, ilości bitów do argumentów funkcji i dodaję warunek stopu:
#include <stdio.h>
#include <limits.h>
unsigned short count_0bits(int value, unsigned short zero_bits, unsigned short bits_counter) {
if (bits_counter == 0) {
return zero_bits;
}
zero_bits += (value & (1 << bits_counter)) ? 0: 1;
return count_0bits(value, zero_bits, --bits_counter);
}
int main(void) {
for (int i = 0; i < 255; ++i) {
printf("%d, num zero bits: %d\n", i, count_0bits(i, 0, CHAR_BIT * sizeof(int)));
}
return 0;
}
Jeśli wiadomo że początkowa wartość bits_counter się nie zmienia, to warto tę wartość startową uczynić stałą.
#include <stdio.h>
#include <limits.h>
#define BITS_IN_INT (CHAR_BIT * sizeof(int))
unsigned short count_0bits(int value, unsigned short zero_bits, unsigned short bits_counter) {
if (bits_counter == 0) {
return zero_bits;
}
zero_bits += (value & (1 << bits_counter)) ? 0: 1;
return count_0bits(value, zero_bits, --bits_counter);
}
int main(void) {
for (int i = 0; i < 255; ++i) {
printf("%d, num zero bits: %d\n", i, count_0bits(i, 0, BITS_IN_INT));
}
return 0;
}
Oczywiście ten kod jest napisany w sposób szkolny :)
Jeśli było by to dopuszczalne, łatwiej rozwiązać zadanie odwrotne. Czyli policzyć jedynki w reprezentacji binarnej. Wystarczy wtedy odjąć od ilości bitów tę ilość jedynek i uzyskujesz ilość zer.
#include <stdio.h>
#include <limits.h>
#define BITS_IN_INT (CHAR_BIT * sizeof(int))
unsigned short count_1bits(int value, unsigned short one_bits) {
return (value ? count_1bits(value >> 1, one_bits + (value & 0x01)): one_bits);
}
int main(void) {
for (int i = 0; i < 255; ++i) {
printf("%d, num zero bits: %ld\n", i, BITS_IN_INT - count_1bits(i, 0));
}
return 0;
}
I teraz po prostym przeniesieniu tej różnicy do funkcji, otrzymasz coś takiego:
#include <stdio.h>
#include <limits.h>
#define BITS_IN_INT (CHAR_BIT * sizeof(int))
unsigned short count_0bits(int value, unsigned short one_bits) {
return (value ? count_0bits(value >> 1, one_bits + (value & 0x01)): BITS_IN_INT - one_bits);
}
int main(void) {
for (int i = 0; i < 255; ++i) {
printf("%d, num zero bits: %d\n", i, count_0bits(i, 0));
}
return 0;
}