Printing to output: integer as sum of powers of 2

Question

I had an exam, and I've been struggling ever since. You have an array of integers(ex. 13, 6, 21, 4), and I need to make an output that looks like:

13 = 2^3 + 2^2 + 2^0
6 = 2^2 + 2^1
21 = 2^4 + 2^2 + 2^0
4 = 2^2

here's what i've got so far.

#include <stdio.h>
#define MAX 100

int main() {
    int niz[MAX], nizb, n, i, ones, k;

    while(1) {
        printf("Array length: ");
        scanf("%d", &n);

        if (n<=0 || n>MAX) break;

        printf("Array elements: ");
        for(i=0;i<n;i++){
            scanf("%d", &niz[i]);
            if (niz[i] <=0) {
                printf("Error! Wrong value. Enter new one: ");
                scanf("%d", &niz[i]);
            }
        }

        for(i=0;i<n;i++) {
            nizb = niz[i];
            ones = 0;

            for(k=0; k < 16; k++) {
                //What should i do here?
            }

        }

    }
}

I'm stuck here. I dont know how many bits should i use, and how does C sees those bits of integer. I'm using var 'k' to add to a string that is in format '2^3 + 2^2 ...', where k is the value of 'for' iteration. I have made an assumption that length of the integer is 16, but im really not sure since we do this on a sheet of paper.

I want to say BIG THANKS TO EVERYONE!!!

Answer 1

Not sure what this has to do with twos-complement (which is a particular way of representing negative numbers). What you are trying to do is express an integer as a sum of powers of 2, apparently. Here's the way I'd do it, which isn't necessarily better or worse than the other answers...

void powersum(int n)
{ int powers[sizeof(int) << 3];
  int i;
  char *sep = "";

  printf("%d = ", n);

  powers[0] = 0;

  for (i = 0; n; n >>= 1, ++i)
    powers[i] = n & 1;

  while (--i >= 0)
  { if (powers[i])
    { printf("%s2^%d", sep, i);
      sep = " + ";
    }
  }

  printf("\n");
}

EDIT: Here's another version that doesn't use the stack-allocated array, but as a tradeoff has to go around the loop more (once for each bit, as opposed to only looping until the highest 1-bit is found):

void powersum2(int n)
{ int i = (sizeof(int) << 3) - 2;
  int m = 1 << i;
  char *sep = "";

  printf("%d = ", n);

  while (m)
  { if (n & m)
    { printf("%s2^%d", sep, i);
      sep = " + ";
    }
    m >>= 1;
    --i;
  }

  printf("\n");
}

Answer 2

You can calculate how many bits to use by using the sizeof operator and CHAR_BIT:

int bitsPerInt = sizeof(int) * CHAR_BIT;

CHAR_BIT is definied in limits.h.

After you have that limit, you can use the bitwise & operator to extract each bit:

for (k = bitsPerInt - 1; k >= 0; k--)
{
    if (nizb & (1U << k))
        // output
    else
        // don't
}

I'll leave the details up to you.

Aside: It looks like you're trying to use niz as an array, but you haven't declared it as one. Does this code even compile? Also, the return value of main should be int.

Answer 3

This is complete conjecture, since I'm not really good with math, but I think I'd go about it like this:

 int potency = 0, base = 1;
 while(base < NumberInQuestion) {
     base *= 2;
     ++potency;
 }

After the loop finishes, you'll know the highest potency which still fits into 'Number'.

 Number -= base/2; //Removes the base you just calculated from the number.
 printf("2^%d", potency);

Rinse and repeat, until Number falls to 0, which should be at 2^0 at latest.

For your use-case, the code may look somewhat like this:

for(i=0; i < n; ++i) {
    int Number = niz[i];
    while(Number > 0) {
        int potency = 0, base = 1;
        do {               //Executes at least once, making a number of '1' possible.
            base *= 2;
            ++potency;
        } while(base < Number);
        Number -= base/2; //Reverts the last step you made, making the 'base' smaller than 'Number'.
        printf("2^%d", potency);
    }
}

There's a possible alternative, which can give you a more complete picture of things and will save you iterations. For this we use a two-step process.

for(i=0; i < n; ++i) {
    int Number = niz[i];
    int potency = 0, base = 1;
    do {               //Executes at least once, making a number of '1' possible.
        base *= 2;
        ++potency;
    } while(base < Number);

    base /= 2;                      //Reverses the last iteration.

    //At this point, we know the maximum potency, which still fits into the number.
    //In regards of base 2, we know the Most Significant Bit.
    while(base > 0) {
        Number -= base;             //Removes the MSD (Most significant digit)
        printf("2^%d", potency);    //Prints your '1'.
        while(base > Number) {      //Executes at least once.
            base /= 2;              //Goes back one potency. (Ends at '0' latest.)
            --potency;              //For each potency (except for first), it's a '0'.
        }
    }
}

Answer 4

quotient = niz[i];
 int k=0,c[MAX];

while(quotient!=0){

     binaryNumber[i++]= quotient % 2;  //this will convert your numbers to binary form 

     quotient = quotient / 2;          //and store in reverse in array

}
for(j = 0 ;j<i;j++)                 
 {                            
     if(binaryNumber[j]==1)  */e.g binary of 4 is stored in array as 001 ie 1 atpos2*/
  {  c[k]=j;
    k++;}
 }
  while(k--)
   printf("2^%d +",c[k]);  

Answer 5

If you can tolerate a GCC-dependency, a hack on @twalberg's solution get's really nice and small ;)

void powersum(int n)
{
    char *sep = "";
    printf("%d = ", n);

    while (n) {
        int pos = 31 - __builtin_clz(n);
        printf("%s2^%d", sep, pos);
        sep = " + ";
        n ^= 1 << pos;
    }

    printf("\n");
}