c++ - 给出 BITS 的总和，找到该数字

Question

问题描述:给你一个数字N，你必须判断是否存在数字K，使得从1到K的所有数字的BITS之和等于N。如果存在则打印该数字，否则打印“不存在”。不带引号。

问题链接:http://www.spoj.com/problems/BIT2/

我的代码复杂度是O((log n)^2)并且获得TLE 人们建议我可以在O(log n)中完成，但我是无法弄清楚。 有人可以帮助我如何在 log n 中执行此操作吗？

下面是我的代码，经过一些预计算 + log(n)^2 这是我所做的。

Solution

Answer 1

提示

您已经快到了，请考虑您的 TotalBits 函数:

LL Total_Bits(LL n)
{  
    if(n==0) return 0;
    LL m = Lmb(n);
    n = n - pow(2,m);
    return (n+1) + Total_Bits(n) + m*pow(2,(m-1));
}

您需要做的是将此函数转换为在给定目标位数的单个调用中计算出 n 的位(从最高有效位到最低有效位)的函数。这允许您从使用二分法中删除对数因子。

如何算出 n 的各位？好吧，假设我们正在尝试计算位置 m 是否需要 1。从代码中可以看出，如果 n>=2**m，则答案至少为 m*pow(2,(m-1)+1，如果 n<2**m，则答案为少一点。

Python代码

def find_index(N):
    """Compute the index K such that sum of all bits in numbers 1..K is N"""
    prefix = 0 # Number of 1's in the answer
    answer = 0 # Lower bound on index K
    for m in xrange(63,-1,-1):
        a = 1 << m
        extra = a*prefix + (m*(1<<m)>>1) # Amount we would add to our count if bit m is set
        if N>extra:
            N -= extra
            prefix += 1
            answer += a
    N-=prefix
    return answer if N==0 else "Does Not Exist."