C++ [Recursive] Write a number as sum of ascending powers of 2

Question

So as the title says,I have to write a number as sum of ascending powers of 2.

For instance, if I input 10, 25 , 173 
10 = 2 + 8
25 = 1 + 8 + 16
173 = 1 + 4 + 8 + 32 + 128

So this is what I have done:

#include <iostream>

using namespace std;

int x,c;
int v[500];

void Rezolva(int putere)
{
    if(putere * 2 <= x)
        Rezolva(putere * 2);

    if(x - putere >= 0)
    {
        c++;
        v[c] = putere;
        x -= putere;
    }

}

int main()
{

    cin >> x;
    c = 0;
    Rezolva(1);

    for(int i = c; i >= 1; i--)
        cout << v[i] << " ";

    return 0;
}

I have a program which gives my code some tests and verifies if it's correct. To one test, it says that I exit the array. Is there any way to get rid of the array or to fix this problem ? If I didn't use the array it would have been in descending order.

The error isn't a compiler error. Caught fatal signal 11 is what I receive when my program checks some tests on the code

[Cannot reproduce](https://wandbox.org/permlink/aVdujjcJx0AZgHhX). What do you insert for `x`? What error message do you get? Please have a look on how to create a [mcve]. — muXXmit2X, Aug 30 '17 at 10:23
_"... that I exit the array ..."_ Do you mean accessing the array out of bounds? To avoid that check `c` is less than 500 before calling `v[c] = putere;`. — user0042, Aug 30 '17 at 10:27
You have come *very* close to providing an MCVE, but we need to know what the input is. Voting to close until you provide it. — Martin Bonner supports Monica, Aug 30 '17 at 10:28
I insert the result. So if I insert 10 , i receive 2 8... If i insert 173 , i receive 1 4 8 32 128 — Vlad-Rares, Aug 30 '17 at 10:29
Note that your array 'v' is vastly bigger than it needs to be. In practise, 63 will be big enough for years. — Martin Bonner supports Monica, Aug 30 '17 at 10:31
I do not know which is the value. I can input number in the range 1 to 10^9 — Vlad-Rares, Aug 30 '17 at 10:33
"To one test, it says that I exit the array." - what value did you give it when that happened? — Martin Bonner supports Monica, Aug 30 '17 at 10:34
@MartinBonner or `int v[sizeof(int) * CHAR_BIT - 1];` to be exactly the right size everwhere — Caleth, Aug 30 '17 at 10:34
No , from 1 to 10^9... I know that c shouldn't be bigger than 500 , but I think it cannot be that big since the max number which can be input is 10^9 which is way smaller than 2^500 — Vlad-Rares, Aug 30 '17 at 10:35
@Caleth : *actually*, there could be an implementation where that is excessive - but it is unlikely, and it will never be insufficient. — Martin Bonner supports Monica, Aug 30 '17 at 10:36
@aerkenemesis I receive what I want for any test I can think of, but somewhere I am accessing the array out of bounds as user0042 said — Vlad-Rares, Aug 30 '17 at 10:39
@Vlad-Rares are you sure the input is from 1 to 10^9 and not to 2 * (10^9)? For any input higher than 10^9 the program crashes. — pmaxim98, Aug 30 '17 at 11:02
@pmaxim98 2 * (10^9) you are right.. Do you know what might cause the crash ? — Vlad-Rares, Aug 30 '17 at 11:05

score 1 · Accepted Answer · answered Aug 30 '17 at 11:07

1

For values higher than 10^9 the program crashes so you need to change from int to long long.

#include <iostream>

using namespace std;

long long x,c;
long long v[500];

void Rezolva(long long putere)
{
    if (putere * 2 <= x)
        Rezolva(putere * 2);

    if (x - putere >= 0)
    {
        v[c++] = putere;
        x -= putere;
    }

}

int main()
{
    cin >> x;
    c = 0;
    Rezolva(1);

    for(int i = c - 1; i >= 0; i--)
        cout << v[i] << " ";

    return 0;
}

All in all, a simple overflow was the cause.

answered Aug 30 '17 at 11:07

pmaxim98

226
2
7

Thanks ! It worked :) Can you tell me where I can read more about overflow or why it didn't worked in the first place ? – Vlad-Rares Aug 30 '17 at 11:22
@Vlad-Rares [This](https://stackoverflow.com/questions/2641285/what-is-an-integer-overflow-error) might be a start, aswell as wikipedia's page about integer overflow. – pmaxim98 Aug 30 '17 at 11:25

score 0 · Answer 2 · answered Aug 30 '17 at 11:29

It was a simple overflow. And by the way a way easier way to do it is have a long long unsigned int

#include <bitset>
unsigned long long x = input;
std::cout << x << " = ";
std::string str = std::bitset<64>(x).to_string();

for (int i = str.size()-1; i >= 0; --i)
    if(str[i]-'0')
        std::cout << (2ull << i) << " + ";

if (x)
    std::cout << char(8)<<char(8) << std::endl;  //DELETING LAST "+" for non-zero x
else
    std::cout << "0\n";

score -1 · Answer 3 · answered Aug 30 '17 at 10:30

If you have a fixed size integer (e.g. int etc.) then you can just start at the greatest possible power of two, and if your number is bigger than that power, subtract the power of 2. Then go to the next power of two.

This is similar to how you would normally write numbers yourself starting from the most significant digit. So also works for how numbers are printed in base 16 (hex), 10, binary literals, etc.

int main() {
    unsigned x = 173;
    std::cout << x << " = ";
    bool first = true;
    // get the max power from a proper constant
    for (unsigned power = 0x80000000; power > 0; power >>= 1)
    {
        if (power <= x)
        {
            if (!first) std::cout << " + ";
            std::cout << power;
            x -= power;
            first = false;
        }
    }
    assert(x == 0);
    std::cout << std::endl;
}

Outputs:

173 = 128 + 32 + 8 + 4 + 1

A better answer than from campovski, but it just does the OP's homework for him, and it doesn't recurse (which is almost certainly a requirement). You also haven't explained the problem with the original code. — Martin Bonner supports Monica, Aug 30 '17 at 10:33
Its just a general way to print integers, i didnt pull apart his code simply because it an entirely different approach, but easy enough to apply to get differnt results. — Fire Lancer, Aug 30 '17 at 10:35

C++ [Recursive] Write a number as sum of ascending powers of 2

3 Answers3