C++解决Hackerrank双置位问题：大二进制字符串取余1000000007

Absolutely! You can definitely calculate the remainder of a huge binary string modulo 1000000007 by working directly with each bit in the string—no need to convert the entire thing to a numeric type (which is what caused your overflow with bitset::to_ullong()). Here's a straightforward, efficient approach:

Core Idea #

A binary number is a sum of powers of 2. Instead of converting the entire string to a giant integer (which overflows standard types), we can compute the remainder incrementally:

• Start with a remainder of 0.
• For each bit in the binary string (from left to right, most significant to least):
  1. Multiply the current remainder by 2 (this simulates shifting the binary number left by one bit, equivalent to multiplying by 2).
  2. Add the value of the current bit (0 or 1).
  3. Take the result modulo 1000000007 to keep the number small and avoid overflow.

This works because modulo operations play nicely with addition and multiplication: (a * b + c) % mod = [(a % mod) * (b % mod) + c % mod] % mod. Since we take the mod at each step, our remainder never exceeds 1000000006—multiplying by 2 gives a maximum value of 2000000012, which fits comfortably in a 64-bit integer (even a 32-bit signed integer can handle this, since 2^31-1 = 2147483647).

Example Implementation (C++) #

#include <iostream>
#include <string>

const int MOD = 1000000007;

long long calculateBinaryMod(const std::string& binary_str) {
    long long remainder = 0;
    for (char bit_char : binary_str) {
        // Update remainder: (current * 2 + bit_value) mod MOD
        remainder = (remainder * 2 + (bit_char - '0')) % MOD;
    }
    return remainder;
}

int main() {
    std::string binary_input;
    std::cin >> binary_input;
    std::cout << calculateBinaryMod(binary_input) << std::endl;
    return 0;
}

Why This Beats bitset #

• bitset requires a fixed size at compile time, which is inflexible for arbitrarily long binary strings.
• to_ullong() can only handle binary numbers that fit into an unsigned long long (typically 64 bits). For longer strings, this will overflow and give incorrect results.
• The string-based approach runs in O(n) time (where n is the length of the binary string) and uses O(1) extra space, making it both efficient and scalable.

内容的提问来源于stack exchange，提问作者Gru