UVa 11744 - Parallel Carry Adder

// UVa 11744 - Parallel Carry Adder

#include <iostream>
#include <string>
using namespace std;

#define integer unsigned long long

integer from_binary(string s) {
	integer n = 0;
	for (int i = 0; i < s.length(); i++)
		n = (n << 1) | (s[i] - '0');
	return n;
}

string to_binary(integer n) {
	string s = "";
	for (int i = 30; i >= 0; i--)
		if (n & (1 << i))
			s += "1";
		else
			s += "0";
	return s;
}

int main() {
	int t;
	for (cin >> t; t; t--) {
		string aa, bb;
		cin >> aa >> bb;
		integer a = from_binary(aa);
		integer b = from_binary(bb);
		integer lim = 2147483648;
		while (b > 0 && b < lim) {
			cout << to_binary(a) << " " << to_binary(b) << endl;
			integer c = a ^ b;
			integer d = a & b;
			a = c;
			b = d << 1;
		}
		if (b >= lim)
			cout << to_binary(a) << " overflow" << endl;
		else
			cout << to_binary(a) << " " << to_binary(b) << endl;
		if (t > 1)
			cout << endl;
	}
	return 0;
}