Hej. Mam napisać kod który zliczy ilość zer w postaci binarnej liczby int. Mam taki kod, który liczy ostatnie "0" w liczbie binarnej . Jak można go przekształcić żeby dostać kod zliczający wszystkie zera w tej liczbie (musi być rekurencja)?
int licz0(int k)
{
if (k==0)
return 1;
if (k%2)
return 0;
else
return 1+licz0(k/2); ```
Zlicza wszystkie zera, nie tylko , które są na końcu
To zarypałeś z netu niewłaściwy kod, ten WYBITNIE liczy od początku i przekształcić go, to strasznie pod górkę.
Masz coś takiego jak sizeof(int). A to wystarczy do (iteracyjnego lub rekurencyjnego) sprawdzenia poszczególnych bitów.
AnyKtokolwiek napisał(a):
Zlicza wszystkie zera, nie tylko , które są na końcu
To zarypałeś z netu niewłaściwy kod, ten WYBITNIE liczy od początku i przekształcić go, to strasznie pod górke
Nie musi być przekształcony ten kod- po prostu myślałem , że ten kod będzie mozna przekształcić na taki , który liczy wszystkie zera.
Obliczanie ilości zer binarnych w liczbie unsigned:
#include <limits.h>
int licz0(unsigned value){
int n;
for(n=0;value != 0;++n){
value = value & (value - 1);
}
return sizeof(unsigned) * CHAR_BIT - n;
}
Riki napisał(a):
Obliczanie ilości zer binarnych w liczbie unsigned:
#include <limits.h> int licz0(unsigned value){ int n; for(n=0;value != 0;++n){ value = value & (value - 1); } return sizeof(unsigned) * CHAR_BIT - n; }
Ale to nie jest chyba rekurencja , czy się mylę?
int countZeroBits(int x)
{
return sizeof(int) * 8 - std::bitset<sizeof(int) * 8>{x}.count();
}
Tu jest wersja rekurencyjna:
unsigned countZeroBits(unsigned x)
{
static std::map<unsigned, unsigned> m{{0,32},{1,31},{3,30},{7,29},{15,28},{31,27},{63,26},{127,25},{255,24},{511,23},{1023,22},{2047,21},{4095,20},{8191,19},{16383,18},{32767,17},{65535,16},{131071,15},{262143,14},{524287,13},{1048575,12},{2097151,11},{4194303,10},{8388607,9},{16777215,8},{33554431,7},{67108863,6},{134217727,5},{268435455,4},{536870911,3},{1073741823,2},{2147483647,1}};
if (m.find(x) != m.end()) return m[x];
for (int i = 31; i; --i) {
if (x & (1u<<i)) {
x ^= 1u<<i;
do {
if ((x & (1u<<(--i)))==0) return countZeroBits(x^(1u<<i));
} while (i > 0);
}
}
}
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;
}