c++ - 计算最小N的置位位数

Question

我正在尝试解决此问题:

Given an integer k, find the least integer n such that the total number of ones in the binary representations of { 1, 2, . . ., n } is at least k.

For example, given k = 4, we want n = 3, because the binary representations of 1, 2, and 3 contain 1, 1, and 2 ones (respectively), and 1 + 1 + 2 ≥ 4.

我尝试使用计数Log(n)中从(1到n)的设置位，无法以有效的方式找到最小值n。
编辑:
代码:计算编号从1到n( Reference)的设置位的位数，但是找到最小n的问题。

int getSetBitsFromOneToN(int N){ 
int two = 2,ans = 0; 
int n = N; 
while(n){ 
    ans += (N/two)*(two>>1); 
    if((N&(two-1)) > (two>>1)-1) ans += (N&(two-1)) - (two>>1)+1; 
    two <<= 1; 
    n >>= 1; 
} 
return ans; 
} 

Answer 1

该算法相对简单。我们将使用一系列函数{a(m)，b(m)，c(m)而不是一次累积一个二进制表示的1的数目，而不是一次累加一个数字。 。}靠近目标，并最多保留几个数字以最后手动添加。每个函数将采用以下格式，其中x是函数的编号(对于a(m)x = 0，对于b(m)x = 1 ...)。

这些函数基于二进制数的特征:在从1到1的所有数字中
您可以在{1,2 ... n}的二进制表示中知道1的累加数。

让我们看一下number，它是二进制1111。您可以知道从1(0001)到15(1111)的所有数字中1的计数-它计算了将1放在4个地方(4)次的多少种方式1，加上可以在2个4位中放置2的次数(6)次2，加上可以在3 4个位置中放置3的次数(4)次3加上可以将4在4位位置中放置的1次次数4.因此，总数为32，也为。您会注意到，对于任何这样的数字n =，累积的1的数目为。让我们根据上面的决定将函数命名为a(m)(此处x = 0，因此无需在此元素中添加元素)。例如:

1 = a(1)= = = =1。

3 = a(2)= = = =4。

7 = a(3)= = = =12。

15 = a(4)= = = = 32.

31 = a(5)= = = = 80.

等等。因此对于数字15，我们计算a(4)并得到32个累加的1。我们还将注意到，数字中恰好有m 1(所有数字均设置为1)。

知道这一点后，您将数字k找出小于k的最接近的a(m)，而a(m + 1)将大于k。如果a(m + 1)仅比k多m + 1，则以a(m + 1)作为答案并完成算法。由于a(m + 1)至少包含m + 2，这意味着如果没有它，您将无法累积所需的所有k 1。

如果k比a(m + 1)大，但大于m + 1，但比a(m)大，则需要通过定义第二个函数来进行第二步近似-将其称为b(m)。我们将定义b(m)=。此数字将完全等于(而不是与a函数相同)，例如:

2 = b(1)= = = = 1 + 2 = 3

4 = b(2)= = = = 4 + 4 = 8

8 = b(3)= = = = 12 + 8 = 20

16 = b(4)= = = = 32 + 16 = 48.

32 = b(5)= = = = 80 + 32 = 112.

我们定义b的原因是为了描述第一批数字与第二批第二批数字之间1的累加的唯一差异-第二批数字中的每个数字都向它们添加另一个最高有效的1。这就是为什么我们现在不看。

通过将两个函数相加，我们可以得到数字n。如果在两次逼近后仍未达到最终k，则可以逐个累加数字，直到达到k。

假设k ＝ 50。我们知道a(4)是我们能够获得的最接近的数字，它是仍低于50的最大数字。如上所述，a(5)将使我们达到80。因此a(4)是解的前半部分，即15。

剩余的1是50-32 = 18。我们需要查看需要处理多少个数字才能累积超过15个1。通过计算b函数，我们看到b(2)使我们更近，而b(3)等于2。因为我们知道b(3)表示的数字中至少有4 1个，所以我们知道这是我们需要的数字-低于它的任何数字都只会累加16 1个，而我们需要18。所以我们选择b(3 )，即8。结果为15 + 8 = 23，这是最低的数字，在所有{1,2..23}二进制表示形式中，至少有50个累加的1。

如果我们需要再进行一次迭代，则可以进行定义，它将使我们更加接近。例如，对于k = 120，我们得到a(5)+ b(3)= 100，加上c(2)将使我们再增加12个到112。我们可以手动添加缺失的8个数字，或者决定添加哪个将得到通过将a(5)+ b(3)+ c(2)+ d(1)添加到119。这意味着下一个数字必须是累计k或大于1的最小n。 a(5)= 31，b(3)= 8，c(2)= 4和d(1)= 2所以n = 46-从119 1收集的下一个数字是45。

复杂度为O(log(k))-我们有log(k)个步骤来获得a(m)，还有另一个log(k)累加来获得b(m)和我们最终的n。

CODE

//This represents the function a(m), b(m)... etc.
public int getFuncResult(int funcNum, int arg) {
    Double result =  Math.pow(2,arg-1)*arg+funcNum*Math.pow(2,arg);
    return result.intValue();
}

//This is the iterative algorithm described: add a(m)+b(m)... until k
public int countOnesToKIter(int k) {
    int funcNum = 0;
    int counter = 0;
    int retVal = 0;
    int exponent = 0;
    while (k > 0) {
        //for the current function, find the appropriate m
        while (k > counter) {
            exponent++;
            counter = getFuncResult(funcNum, exponent);
        }

        //if the last number contains more 1's than the difference, use it.
        if (counter-k < exponent) {
            counter=getFuncResult(funcNum, exponent-2);
            retVal+=Math.pow(2,exponent-2);
        } else {
            counter = getFuncResult(funcNum, exponent-1);
            retVal+=Math.pow(2,exponent-1);
        }
        funcNum ++;
        exponent=0;
        k = k-counter;
        counter = 0;
    }

    return retVal;
}