模运算未返回正确值

Question

我正在尝试解决 leetcode 中的一个问题，我破解了该特定问题的算法，编写了伪代码，并用 C++ 实现了代码。解决方案中只剩下一个缺陷，modulo 1e9+7 结果。

问题陈述：给定一个整数 n，return 通过按顺序连接 1 到 n 的二进制表示形式的二进制字符串的十进制值，模 1e9 + 7。

我的做法：

我的代码：

#include<math.h>
class Solution {
public:
    int concatenatedBinary(int n) {
        long long res = 0;
        for(int i=0;i<n;i++){
            int lShift = (int)ceil(log((double)(i+1+1)));
            res = res << lShift;
            //problem lies between these 
            res %= 1000000007;
            res += i+1;
            res %= 1000000007;
            cout << i << " - " << lShift << " - " << res << endl;
        }
        return res;
    }
};

我不知道为什么模运算表现得很奇怪！提前致谢。

Example 1:

Input: n = 1
Output: 1
Explanation: "1" in binary corresponds to the decimal value 1. 

Example 2:

Input: n = 3
Output: 27
Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11".
After concatenating them, we have "11011", which corresponds to the decimal value 27.

Example 3:

Input: n = 12
Output: 505379714
Explanation: The concatenation results in "1101110010111011110001001101010111100".
The decimal value of that is 118505380540.
After modulo 109 + 7, the result is 505379714.

Answer 1

您的主要问题是您使用 log 而不是以 2 为底的对数：log2.

此外，这种情况一般最好避免浮点计算。

在下面的代码中，我包含了您的代码的更正版本，
和一个没有任何浮点计算的新的简单版本


#include<cmath>
#include <iostream>

class Solution {
public:
    int concatenatedBinary(int n) {
        long long res = 0;
        for(int i = 0; i < n; i++){
            int lShift = (int)ceil(log2((double)(i+1+1)));
            res = res << lShift;
            //problem lies between these 
            res %= 1000000007;
            res += i+1;
            res %= 1000000007;
            std::cout << i+1 << " - " << lShift << " - " << res << std::endl;
        }
        return res;
    }
    int concatenatedBinary_nolog(int n) {
        long long res = 0;
        int lShift = 1;
        int pow2 = 2;
        for(int i = 1; i <= n; i++){
            if (i >= pow2) {
                lShift++;
                pow2 *= 2;
            }
            res = res << lShift;
            res %= 1000000007;
            res += i;
            res %= 1000000007;
            std::cout << i << " - " << lShift << " - " << res << std::endl;
        }
        return res;
    }
};

int main(){
    Solution sol;
    for (int n: {1, 3, 12}) {
        int answer = sol.concatenatedBinary(n);
        std::cout << n << " : " << answer << "\n";
        answer = sol.concatenatedBinary_nolog(n);
        std::cout << n << " : " << answer << "\n";
    }
}

模运算未返回正确值

modulo operation not returning correct value

c++

bit-shift

modulo

modular-arithmetic