打印输出：整数作为2的幂的总和

Question

我参加了一次考试，从那以后我一直在努力奋斗。 你有一个整数（如13，6，21，4）的数组，我需要做的输出，看起来像：

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

这里就是我这么远。

#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? 
      } 

     } 

    } 
} 

我被困在这里。我不知道应该使用多少位，以及C如何看到这些整数的位。我使用var'k'来添加格式为'2^3 + 2^2 ...'的字符串，其中k是'for'迭代的值。我假定整数的长度是16，但我真的不确定，因为我们在一张纸上做了这个。

我想说的是感谢所有人！

Answer 1

不知道这与两个补码（这是一种表示负数的特殊方式）有什么关系。显然，你要做的是将整数表示为2的幂的和。这就是我要做的方式，不一定比其他答案更好或更差...

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"); 
} 

编辑：这是另一个不使用堆栈分配数组版本，但是作为一个折衷方案具有去各地环以上（一次为每个比特，而不是唯一的循环，直至最高1位被发现）：

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

你可以计算出多少位使用sizeof运营商和CHAR_BIT使用方法：

int bitsPerInt = sizeof(int) * CHAR_BIT; 

CHAR_BIT在limits.h被definied。

之后，你有这个限制，你可以使用按位&操作人员提取每个位：

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

我会离开的细节给你。

另外：它看起来像你试图使用niz作为一个数组，但你没有声明它为一个。这段代码是否可以编译？此外，main的返回值应为int。

Answer 3

这完全是猜测，因为我不是数学真的很不错，但我想我会去了解它是这样的：

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

循环结束后，你就会知道的最高效能这仍然适合'数字'。

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

冲洗并重复，直到Number降到0，最迟应为2^0。

为您的使用情况，代码可能看起来有点像这样：

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); 
    } 
} 

有一种可能的选择，它可以给你的东西更完整的画面，将节省您的迭代。为此我们使用两步过程。

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

如果你能忍受一个GCC的依赖，对@ twalberg的解决方案一劈得到的真的很好，小;）

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"); 
}