Problem z funkcją zliczającą jedynki

Question

Funkcja ma zliczyć sumę jedynek w reprezentacji binarnej wszystkich liczb z tablicy. Wiem, że problem z jej działaniem wynika z wyzerowania counter na początku, ale niestety nie wiem jak to naprawić 

long int Ones(long int array[], int size){
    int counter = 0;
    unsigned int mask = 1;
    for(int i = 0; i < 32; i++){
        if (array[size-1] bitand mask) {
            counter++;
        }
        mask <<= 1;
    }
    if (size>=1) Ones(array, size-1);
    return counter;
}

 

Comments

czemu nie uzyjesz std::count, std::count_if?

---

niestety prowadzący nie pozwala

---

W takim rszie, przekazuj ilosc obecnych jedynek, skoro chcesz to robic rekurencja, a nie petla

Answer 1

size_t Ones(long int array[], size_t size, size_t count = 0){
    if (size == 0) {
        return count;
    }
    --size;
    while(array[size] != 0) {
        count += array[size] & 0x01;
        array[size] >>= 1;
    }
    return Ones(array, size, count);
}

 

Comments

dziękuję!

---

Wiesz, w zasadzie da się to napisać jeszcze sprytniej z użyciem dodatkowej rekurencji. Nie sądzę by jednak to było czytelne. C ani C++ nie nadają się za bardzo do takich eksperymentów:

unsigned CountInInt(int value, unsigned count = 0) {
    return value != 0 ? count += value & 0x01, CountInInt(value >> 1, count): count;
}

size_t Ones(long int array[], size_t size, size_t count = 0){
    return size != 0 ? --size, Ones(array, size, CountInInt(array[size], count)): count;
}

 

Answer 2

Użyj algorytmu Brian Kernighan`s

size_t count_ones( size_t array[], int size )
{
    size_t counter {0};
    for( int i=0 ; i<size ; ++i )
    {
        for( size_t element = array[i]; element ; ++counter )
        {
          element &= element-1;
        }
    }

    return counter;
}

 

Comments

Cos czuje, ze to zadanie na rekurencje z jakiegos uniwerku

---

Zawsze można sobie przerobić pętlę na rekurencję.

---

@DragonCoder, a jednak polibuda ;) 
 

---

@TOM_CPP, rekurencja jest konieczna, a metoda musi bazować na operatorach bitowych, więc niestety nic mi to nie pomogło

---

"Metoda" bazuje na operatorze bitowym &. Chyba że prowadzący zajęcia wprowadził wymóg użycia wszystkich możliwych operatorów bitowych.

 

---

wszystkich możliwych to nie, ale przynajmniej dwa