不实际计算1的数量，打印序列中某个数之前所有数字中1的个数。

Question

一个面试题:

编写一个程序，该程序接收输入参数 'N'（一个无符号长整数），并打印两列输出。第一列以十六进制格式打印从1到N的数字；第二列打印左侧数字在二进制表示中出现的1的数量。条件是这个程序不应计算1的数量（因此不能对每个数字进行计算/没有除法运算符）。

我尝试通过利用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

- Manish Baphna

---

没有任何理由关闭这个帖子，尤其是因为楼主已经尽力解决问题并发布了他最好的解决方案。 - Alok Save

这个问题可能更适合在codereview.stackexchange.com上进行讨论。 - RedX

也许你可以粘贴一下输出是什么样子的？ - Kev

@redx 我会向代码审查人员咨询，看看他们的想法。 - Kev

@yasouser：这意味着，如果我们输入“N”，则在循环的“N”次迭代中，我们应该得到结果。如果我们尝试通过计数来计算“1s”，那么总迭代次数将是Sum(Mx)，其中x从1到N，m是用于计算数字中的“1s”的“迭代”次数。 - Manish Baphna

Answer 1

我有一种略微不同的方法，可以解决您的内存问题。它基于这样一个事实：按位运算符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;
}

希望这个更好地运作。

- kyun

---

终止条件应该是 j= j - (j&-j)。这是一种好的方法，但不符合“不计算每个数字中的1”的条件。 - Manish Baphna

我想我明白你的意思了。好的，正在编辑帖子以使用动态编程方法。现在稍等。 - kyun

实际上，我现在没有其他的东西了 - 抱歉！如果我能想到更好的东西，我会发布一些内容。 - kyun

新增了一种更好的方法 - 这有帮助吗？ - kyun

考虑到N可能是2^32这么大的数字（ULong至少有这个大小），DP的内存需求是不合理的。其他基于数组的解决方案也是如此。请参见我的解决方案，使用递归进行深度优先搜索二进制位树，其中从根到叶子的位模式对应于32位整数。深度优先搜索按顺序产生0..2^32的整数。只需在到达叶子时计算“1”位数即可得到答案。 - NealB

Answer 2

到目前为止，发布的几个答案都使用了位移（只是除以2的另一个词）或位掩码。这让我感到有点欺骗。同样适用于在4位模式中使用“1”位计数，然后通过4位块进行匹配。

如何使用虚拟二进制位树的简单递归解决方案呢？每个左分支包含一个“0”，每个右分支包含一个“1”。然后进行深度优先遍历，在下行的过程中计算1位的数量。一旦到达树的底部，将计数器加1，打印出迄今为止找到的1位数，向上退回一个级别并再次递归。

当计数器达到所需数字时停止递归。

我不是C/C++程序员，但这里是一个REXX解决方案，不需要太多想象即可转换。注意，神奇的数字32只是无符号长整型中的位数。将其设置为任何值。

/* 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

这个答案在时间和空间上都相当高效。

- NealB

---

我也喜欢这个解决方案。我最初认为你会遇到堆栈溢出问题，但是由于最大深度为32，应该没问题！回溯很漂亮 +1 - kyun

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

- Chad

---

我喜欢这个解决方案。就内存而言，我认为这是你能得到的最好的。然而，我理解不计算位数就意味着不一次处理一个数字——这是我唯一看到的潜在缺陷。 - kyun

Answer 4

解释

以下算法与您的算法类似，但是扩展了这个想法（如果我正确理解了您的方法）。它不会按照问题指示进行任何“每个数字”的计算，而是使用长度为2的幂的序列之间存在的递归。基本上，观察到对于序列0, 1,..,2^n-1，我们可以使用序列0, 1, ...,2^(n-1)-1来进行以下操作。

设f(i)是数字i中的1的数量，则对于所有0<=i<2^(n-1)，有f(2^(n-1)+i)=f(i)+1。（请自行验证）

C++中的算法

#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，可能会溢出到负数，否则如果你想超过这个数字，请使用无符号整数。

效率

此算法的运行时间为O(N)，空间复杂度为O(N)。

- ldog

Answer 5

这里有一种时间复杂度为O(nlogn)，内存使用量为O(1)的方法。思路是获取数字的十六进制等效值，并迭代它以获取每个十六进制位上的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;

}

- Shamim Hafiz - MSFT

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

- MSN