Print number of 1s in a sequence upto a number , without actually counting 1s
An interview question :

Make a program which takes input 'N'(unsigned long) and prints two columns,1st column prints numbers from 1 to N and second column prints Number of 1s in left column. Condition is that this program should not count 1s ( so no computations 'per number' to get 1s/ no division operators). 

I tried to implement this by leveraging fact that No of 1s in 0x0 to 0xF can be re-used to generate 1s for any number. I am pasting code ( basic one without error checking.) Its giving correct results but I am not happy with space usage. How can I improve on this ?
(  Also I am not sure if its what interviewer was looking for ). 

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


Print number of 1s in a sequence upto a number , without actually counting 1s
===

An interview question :

Make a program which takes input 'N'(unsigned long) and prints two columns,1st column prints numbers from 1 to N and second column prints Number of 1s in left column. Condition is that this program should not count 1s ( so no computations 'per number' to get 1s/ no division operators). 

I tried to implement this by leveraging fact that No of 1s in 0x0 to 0xF can be re-used to generate 1s for any number. I am pasting code ( basic one without error checking.) Its giving correct results but I am not happy with space usage. How can I improve on this ?
(  Also I am not sure if its what interviewer was looking for ). 

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

