在一个序列中打印1到1的数字,而不实际计算1

Question

面试问题:

制作一个输入'N'(无符号长)并打印两列的程序,第一列打印从1到N的数字(十六进制格式),第二列打印左列中数字的二进制表示中的1的数量.条件是这个程序不应该计数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;
    }

}

编辑添加样本运行

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

Answer 1

我有一个稍微不同的方法,可以解决你的记忆问题.它基于以下事实:按位运算i & -i为您提供数字中最小的2的幂i.例如,对于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;
}

希望这更好