Распечатайте номер 1 с в последовательности до номера, без фактического подсчета 1 с

Ответ 1

У меня есть несколько иной подход, который должен решить вашу проблему с памятью. Его основано на том факте, что побитовая операция i & -i дает наименьшую мощность двух в числе 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;
   }
}

Надеюсь, я правильно понял ваш вопрос. Надеюсь, что поможет

Edit: Хорошо, попробуйте это - это динамическое программирование без использования каждого бита в каждом номере:

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

Надеюсь, это работает лучше

Ответ 2

В нескольких ответах, опубликованных до сих пор, используется смещение битов (просто другое слово для деления на 2) или бит. Это походит на меня как на обманщика. То же самое касается использования количества бит "1" в 4-битной схеме, тогда сопоставление кусками 4 бит.

Как насчет простого рекурсивного решения с использованием воображаемого бинарного дерева бит. каждая левая ветвь содержит "0", каждая правая ветвь содержит "1". Затем сделайте глубину первого обхода, подсчитывая количество 1 бит по пути вниз. однажды дно дерева достигнуто, добавьте один к счетчику, распечатайте количество найденных 1 битов, отбросьте назад на одном уровне и повторить процедуру.

Остановите рекурсию, когда счетчик достигнет желаемого номера.

Я не программист на C/С++, но вот решение REXX, которое должно переводить без особого воображения. Заметка магическое число 32 - это просто количество бит в Unsigned long. Установите его на что-нибудь

/* REXX */

SAY 'Stopping number:'
pull StopNum

Counter = 0
CALL CountOneBits 0, 0
return

CountOneBits: PROCEDURE EXPOSE Counter StopNum
ARG Depth, OneBits

   If Depth = 32 then Return              /* Number of bits in ULong */
   if Counter = StopNum then return       /* Counted as high as requested */
   call BitCounter Depth + 1, OneBits     /* Left branch is a 0 bit */
   call BitCounter Depth + 1, OneBits + 1 /* Right branch is a 1 bit */
   Return

BitCounter: PROCEDURE EXPOSE Counter StopNum
ARG Depth, OneBits

   if Depth = 32 then do            /* Bottom of binary bit tree */
      say D2X(Counter) 'contains' OneBits 'one bits'
      Counter = Counter + 1
      end
   call CountOneBits Depth, OneBits
  return    

Результаты:

Stopping number:
18
0 contains 0 one bits
1 contains 1 one bits
2 contains 1 one bits
3 contains 2 one bits
4 contains 1 one bits
5 contains 2 one bits
6 contains 2 one bits
7 contains 3 one bits
8 contains 1 one bits
9 contains 2 one bits
A contains 2 one bits
B contains 3 one bits
C contains 2 one bits
D contains 3 one bits
E contains 3 one bits
F contains 4 one bits
10 contains 1 one bits
11 contains 2 one bits

Этот ответ резонно эффективен во времени и пространстве.

Ответ 3

Может быть сделано относительно тривиально в постоянное время с соответствующим переключением бит. Нет подсчета 1-го и без дивизий. Я думаю, что вы были на правильном пути с сохранением массива известных значений бит:

int bits(int x)
{
   // known bit values for 0-15
   static int bc[16] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};

   // bit "counter"
   int b = 0;
   // loop iterator
   int c = 0;

   do
   {
      // get the last 4 bits in the number
      char lowc = static_cast<char>(x & 0x0000000f);

      // find the count
      b += bc[lowc];

      // lose the last four bits
      x >>= 4;

      ++c;

      // loop for each possible 4 bit combination,
      // or until x is 0 (all significant bits lost)
   }
   while(c < 8 && x > 0);

   return b;
}

Ответ 4

Описание

Следующий алгоритм похож на ваш, но расширяет идею (если я правильно понял ваш подход.) Он не выполняет никаких вычислений "за число" в соответствии с вопросом, а вместо этого использует рекурсию, существующую между последовательностями длины которых равны степеням 2. В принципе наблюдение состоит в том, что для последовательности 0, 1,..,2^n-1 мы можем использовать последовательность 0, 1, ...,2^(n-1)-1 следующим образом.

Пусть f(i) - число единиц в числе i, затем f(2^(n-1)+i)=f(i)+1 для всех 0<=i<2^(n-1). (Проверьте это для себя)

Алгоритм в С++

#include <stdio.h>
#include <stdlib.h>

int main( int argc, char  *argv[] )
{
   const int N = 32;

   int* arr = new int[N];
   arr[0]=0;
   arr[1]=1;
   for ( int i = 1; i < 15; i++ )
   {
      int pow2 = 1 << i;
      int offset = pow2;
      for ( int k = 0; k < pow2; k++ )
      {
         if ( offset+k >= N )
            goto leave;
         arr[offset+k]=arr[k]+1;
      }
   }

leave:

   for ( int i = 0; i < N; i++ )
   {
      printf( "0x%8x %16d", i, arr[i] );
   }

   delete[] arr;
   return EXIT_SUCCESS;
}

Обратите внимание, что в цикле for

   for ( int i = 0; i < 15; i++ )

может быть переполнение на отрицательные числа, если вы выходите выше 15, иначе используйте unsigned int, если вы хотите пойти выше этого.

Эффективность

Этот алгоритм работает в O(N) и использует пространство O(N).

Ответ 5

Вот подход, который имеет O (nlogn) временную сложность и O (1) использование памяти. Идея состоит в том, чтобы получить шестнадцатеричный эквивалент числа и перебрать его, чтобы получить число единиц на шестнадцатеричную цифру.

int oneCount[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};

int getOneCount(int n)
{
  char inStr[70];
  sprintf(inStr,"%X",n);
 int i;
int sum=0;
for(i=0; inStr[i];i++)
{
 if ( inStr[i] > '9' )
  sum += oneCount[inStr[i]-'A' + 10];
else
 sum+= oneCount[inStr[i] -'0'];
}
return sum;

}

int i,upperLimit;
cin>>upperLimit;

for(i=0;i<=upperLimit;i++)
{
 cout << std::hex << " num = " << i << std::dec << "   number of 1s = " << getOneCount(i) << endl;

}

Ответ 6

enum bit_count_masks32
{
    one_bits= 0x55555555, // 01...
    two_bits= 0x33333333, // 0011...
    four_bits= 0x0f0f0f0f, // 00001111....
    eight_bits= 0x00ff00ff, // 0000000011111111...
    sixteen_bits= 0x0000ffff, // 00000000000000001111111111111111
};

unsigned int popcount32(unsigned int x)
{
    unsigned int result= x;
    result= (result & one_bits) + (result & (one_bits << 1)) >> 1;
    result= (result & two_bits) + (result & (two_bits << 2)) >> 2;
    result= (result & four_bits) + (result & (four_bits << 4)) >> 4;
    result= (result & eight_bits) + (result & (eight_bits << 8)) >> 8;
    result= (result & sixteen_bits) + (result & (sixteen_bits << 16)) >> 16;

    return result;
}

void print_range(unsigned int low, unsigned int high)
{
    for (unsigned int n= low; unsigned int n<=high; ++n)
    {
        cout << std::hex << " num = " << xcount << std::dec << "   number of 1s = " << popcount32(n) << endl;
    }
}