Вывести количество единиц в последовательности вплоть до числа, без фактического подсчета единиц [закрыто]

Трудно сказать, о чем здесь спрашивают. Этот вопрос неоднозначный, расплывчатый, неполный, чрезмерно широкий или риторический, и на него нельзя разумно ответить в его нынешней форме. Чтобы прояснить этот вопрос и снова открыть его, посетите справочный центр .

Закрыто 8 лет назад .

Вопрос для собеседования:

Создайте программу, которая принимает ввод «N» (длинное беззнаковое число) и печатает два столбца, в первом столбце печатаются числа от 1 до N. (в шестнадцатеричном формате), а во втором столбце печатается количество единиц в двоичном представлении числа в левом столбце . Условие состоит в том, что эта программа не должна считать единицы (так что никаких вычислений «на число» для получения единиц / без операторов деления).

Я попытался реализовать это, используя тот факт, что ни одна из единиц в 0x0 - 0xF не может быть повторно использована для генерации единиц для любого числа. Я вставляю код (базовый, без проверки ошибок). Он дает правильные результаты, но меня не устраивает использование места. Как я могу это улучшить? (Также я не уверен, что это искал интервьюер.)

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

задан Cœur 3 September 2017 в 11:54

0 ответов

Другие вопросы по тегам:

c++ algorithm puzzle

Вывести количество единиц в последовательности вплоть до числа, без фактического подсчета единиц [закрыто]

0 ответов

Похожие вопросы: