I’m working on a problem where I need to find the minimum terms to represent an integer n as a Sum of Powers of 2 and Negative Powers of 2.

The input would be a binary string representative of the integer n.

For example, with input 1101101 as binary or 109 as decimal. Minimum terms are:

• 109 = 2⁷ – 2⁴ – 2² + 2⁰
  Output would be 4. (4 terms)

My current code works well for smaller values of n, specifically for n up to 2¹²⁸ – 1, but I need the variable n be able to handle up to 2^1048576 – 1 '1048576-bit integer' – if you will.

My current approach:

#include <iostream>
#include <string>

int main() {
    std::ios_base::sync_with_stdio(false); 
    std::cin.tie(nullptr); 
    std::cout.tie(nullptr);

    std::string bin_str;
    std::cin >> bin_str; //Input of binary string equivalent of integer n.

    int result = 0;
    unsigned __int128 n = 0;

    for (char c : bin_str) {
        n = (n << 1) | (c - '0');
    }
    
    //Converting into decimal

    while (n) { //I'll try to clear up the logic for this while loop below.
        ++result;
        n = (n + (n & -n)) & ~((n & -n) << 1);
    }

    std::cout << result;
    return 0;
}

For the while loop logic, basically I’m adjusting the integer n by removing the lowest set bit.

• n + (n & -n) finds the bit, isolates it and adds to n.

• ~((n & -n) << 1) excludes the next higher power of 2 by negating and shifting the isolated bit.

Any help or suggestions on how to deal with such large integers 2^1048576 – 1 in C/C++ would be greatly appreciated. A more efficient algorithm would do wonders for me too.