# Handling addition of two binary numbers

This code is for handling addition of two binary numbers, which can be as long as 100,000 bits... and up to 500,000 queries are performed.

High-level pseudocode:

1. First input N: number of bits in binary number A and B.
2. Second input Q: number of queries to be performed.
3. Next N inputs: 0/1s ... bits for A
4. Next N inputs: 0/1s ... bits for B
5. Next Q inputs are one of the following:

1. set_a INDEX VALUE: as a result I set a[INDEX] = VALUE
2. set_b INDEX VALUE: as a result I set b[INDEX] = VALUE
3. get_c INDEX: as a result I print c[INDEX] where C = A+B (binary addition, like 100 + 101 = 1001)

#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#include <utility>  // For pair
#include <iterator> // For iterator, bidirectional_iterator_tag, reverse_iterator
#include <climits>  // For CHAR_BIT, ULONG_MAX
using namespace std;

class VanEmdeBoasTree {};

int main(int argc, char * argv[])
{
int n, q;
char c;
bool a[100005] = {0}, b[100005] = {0};
VanEmdeBoasTree equals;
cin>>n;
cin>>q;

for(int i=0;i<n;i++){
cin>>c;
if(c=='1')
a[n-i-1] = true;
}
for(int i=0;i<n;i++){
cin>>c;
if(c=='1')
b[n-i-1] = true;
if(a[n-i-1] == b[n-i-1]){
equals.insert(n-i-1);
}
}

string query;
int index, val, lastval;
for(int i=0;i<q;i++){
cin>>query;
cin>>index;
if(query[4] == 'a'){
cin>>val;
if(a[index] != val){
a[index] = val;
if(a[index] == b[index]){
equals.insert(index);
}else{
equals.erase(index);
}
}
}else if(query[4] == 'b'){
cin>>val;
if(b[index] != val){
b[index] = val;
if(a[index] == b[index]){
equals.insert(index);
}else{
equals.erase(index);
}
}
}else if(query[4] == 'c'){
int final = 0;
if(index == n){
if(equals.size() > 0){
VanEmdeBoasTree::const_iterator it = equals.predecessor(index+1);
if(it!=equals.end() && a[*it] == 1){
final = 1;
}
}
}else{
final = (a[index] + b[index])%2;
if(equals.size() > 0){
VanEmdeBoasTree::const_iterator it = equals.predecessor(index);
int last = -1;
if(it != equals.end())
last = *it;
if( last!=-1 && index!=0 && it!=equals.end() &&  a[last] == 1){
final = 1-final;
}
}
}
cout<<final;
}
}

return 0;
}


My solution is not fast enough as the Judge says "time out" after some test cases.

• Can you link the online judge for this problem? Commented Jan 30, 2012 at 19:21
• @WinstonEwert its the same one posted in one of the issues raised in meta.codereview.stackexchange.com by you. :-/ Commented Jan 30, 2012 at 19:28

Profile and you will find your bottlenecks, you can do that with gprof under gcc/g++. You have to set the -g -pg on compile and then run your program like you would do normally. It will then produce a gmon.out file which you can open with gprof main gmon.out (assuming main is the name of your executable).

It will show you, in which functions your program spends most of the time.

• The code in is C++ and gcc wont compile it, i tired what you said with g++ but no gmon.out was created. Commented Jan 30, 2012 at 19:20
• @Pheonix Oh, I forgot, you have to add -g.
– inf
Commented Jan 30, 2012 at 19:28
• @Pheonix: The gmon.out is generated after you run the program. Commented Jan 30, 2012 at 23:34

I've just solved this problem (using a different technique then you)

Things I learned that you might find useful:

1. There is a lot of input for the test cases. I found that I was spending the bulk of my time just reading in the input. However, this didn't didn't show up in the output of gprof
2. I had to construct test cases with pathalogical natures to find the performance issues with my solution.
• congratulations... but on the other hand, i am struggling a lot, i changed quiet a few things, not using stl::map anymore, my own testcases are coming fine, tested with hundreds of them now, but wrong answer after #5... and its been 2 days with that :( am out of test cases Commented Feb 1, 2012 at 18:24
• @Pheonix, if you share the latest version of the code, I'll see if I can pinpoint where yours fails Commented Feb 1, 2012 at 18:32
• i updated my code in the question, removed the implementation of VanEmdeBoasTree from code, keithschwarz.com/interesting/code/?dir=van-emde-boas-tree .. i dont get timeout (thanks to van-emde-boas), but wrong answer. Commented Feb 1, 2012 at 19:02
• additionally, there is one more implementation with some changes, which i made to make testing easier, it sets random bits and A/B and prints all A, B, C... so i see if result is matching or not, if u wish i will post that code too. Commented Feb 1, 2012 at 19:04
• @Pheonix, your code doesn't print a newline after all the bits. Other then that, I haven't found a case where my version differs. Commented Feb 1, 2012 at 19:36