c++ - 按顺序打印1s(最多1个数字)，而不实际计数1s

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center。




9年前关闭。




面试题:

制作一个使用输入'N'(无符号长整数)并打印两列的程序，第一列打印从1到N的数字(十六进制格式)，第二列打印左数的二进制表示形式的1s列。条件是该程序不应计数为1s(因此，没有“按数字计算”获得1s/没有除法运算符)。

我试图通过利用以下事实来实现这一点:可以将0x0到0xF中的1的任何一个都重复使用以为任何数字生成1。我正在粘贴代码(没有错误检查的基本代码)。它给出了正确的结果，但我对空间使用情况不满意。我该如何改善？
(同样，我不确定其面试官在寻找什么)。

void printRangeFasterWay(){

    uint64_t num = ~0x0 ;
    cout << " Enter upper number " ;
    cin >> num ;

    uint8_t arrayCount[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4} ;
    // This array will store information needed to print
    uint8_t * newCount = new uint8_t[num] ;
    uint64_t mask = 0x0 ;
    memcpy(newCount, &arrayCount[0], 0x10) ;

    uint64_t lower = 0;
    uint64_t upper = 0xF;
    uint64_t count = 0 ;
    uint32_t zcount= 0 ;

    do{
      upper = std::min(upper, num) ;

      for(count = lower ; count <= upper ; count++){
         newCount[count] = (uint32_t)( newCount[count & mask] + newCount[(count & ~mask)>>(4*zcount)]) ;
      }
      lower += count  ;
      upper |= (upper<<4) ;
      mask =   ((mask<<4) | 0xF ) ;
      zcount++ ;
    }while(count<=num) ;

    for(uint64_t xcount=0 ; xcount <= num ; xcount++){
       cout << std::hex << " num = " << xcount << std::dec << "   number of 1s = " << (uint32_t)newCount[xcount] << endl;
    }

}

编辑以添加 sample 运行

Enter upper number 18
 num = 0   number of 1s = 0
 num = 1   number of 1s = 1
 num = 2   number of 1s = 1
 num = 3   number of 1s = 2
 num = 4   number of 1s = 1
 num = 5   number of 1s = 2
 num = 6   number of 1s = 2
 num = 7   number of 1s = 3
 num = 8   number of 1s = 1
 num = 9   number of 1s = 2
 num = a   number of 1s = 2
 num = b   number of 1s = 3
 num = c   number of 1s = 2
 num = d   number of 1s = 3
 num = e   number of 1s = 3
 num = f   number of 1s = 4
 num = 10   number of 1s = 1
 num = 11   number of 1s = 2
 num = 12   number of 1s = 2

最佳答案

我有一个略有不同的方法，应该可以解决您的内存问题。它基于以下事实:按位运算i & -i在i中为您提供最小的2的幂。例如，对于i = 5，i & -i = 1，对于i = 6，i & -i = 2。现在，获取代码:

void countBits(unsigned N) {
   for (int i = 0;i < N; i ++)
   {
       int bits = 0;
       for (int j = i; j > 0; j= j - (j&-j))
           bits++;
       cout <<"Num: "<<i <<" Bits:"<<bits<<endl;
   }
}

希望我能正确理解您的问题。希望能有所帮助

编辑:
好的，尝试一下-这是动态编程，无需使用每个数字中的每一位:

void countBits(unsigned N) {
   unsigned *arr = new unsigned[N + 1];
   arr[0]=0;
   for (int i = 1;i <=N; i ++)
   {
       arr[i] = arr[i - (i&-i)] + 1;
   }
   for(int i = 0; i <=N; i++)
    cout<<"Num: "<<i<<" Bits:"<<arr[i]<<endl;
}

希望这更好

关于c++ - 按顺序打印1s(最多1个数字)，而不实际计数1s，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7077073/