BINADD - Editorial

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Alexey Zayakin
Tester: Ildar Gainullin
Editorialist: Oleksandr Kulkov

DIFFICULTY:
EASY
PREREQUISITES:
Basic binary operations
PROBLEM:
Consider the following function written in pseudo-code:

function add(A, B):
    while B is greater than 0:
        U = A XOR B
        V = A AND B
        A = U
        B = V * 2
    return A

You’re given binary numbers A and B and have to tell the number of times inner loop is repeated.
QUICK EXPLANATION:
Calculate the length of the longest carry chain.
EXPLANATION:
Basically this representation means that U is digit-wise sum and V is carry. We may interpret the whole process as if we simultaneously started addition in all points and carried excessive bits in all places at the same time. We can get the whole time of the process by some case-work. Let’s simulate simple addition with carry. Let’s look closely on the number carry_i + A_i + B_i.

  • If it’s equal to 0 or 1 then it won’t affect the carrying process.
  • If it’s equal to 2 then we either initiate carrying process with A_i=B_i=1 or continue it with having carry=1 and either of A_i and B_i being equal to 1.
  • Finally, if it’s equal to 3 then carrying process will start from scratch as after first xor there will be 0 on i-th place and carry_i will simply drop here, while some new carry from A_i + B_i will go on (i+1)-th bit.

Thus, the answer to the problem can be obtained by carefully simulating the process. You should also take an extra look on B=0 case.

void solve() {
	// Aligning and reversing bits of A and B
	string A, B;
	cin >> A >> B;
	reverse(begin(A), end(A));
	reverse(begin(B), end(B));
	while(A.size() < B.size()) A += "0";
	while(B.size() < A.size()) B += "0";
	A += "0"; B += "0";
	// actual solution is below
	int carry = 0, ans = 0, cur = 0;
	for(size_t i = 0; i < A.size(); i++) {
		carry = carry + (A[i] - '0') + (B[i] - '0');
		if(carry > 1) {
			cur++;
		} else {
			cur = 0;
		}
		carry /= 2;
		ans = max(ans, cur);
	}
	cout << ans + (B.find('1') != string::npos) << endl;
}

AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

6 Likes

How is the length of the longest carry chain the number of times the inner loop is repeated?

2 Likes

@thethinker01 It’s hard to explain in words.
Take 2 random binary with different carry lengths and add them yourself using the method in question. You’ll surely understand

1 Like

The algorithm in the problem statement replicates the n-bit binary addition as implemented by multiple full adders (only here you can think of them working in parallel in contrast to the propagation delay factor in the actual hardware).

The XOR of the two bit-strings (holding binary numbers) in an iteration gives you the sum of the two exclusive of the carries (if any generated) in this iteration. Now we identify the set of bits that generates carry in this iteration and we do so by AND-ing the two bit-strings (the 1’s at the least significant ith bit indicates that the one-bit sum at ith bit generated a carry which needs to be resolved). Now we know the positions where the carries are generated and we know that the carries are resolved by forwarding them to an immediate higher position from where they’re generated (to a position which is more significant by one bit). It means that the carry generated at ith bit will be resolved at (i + 1)th bit. So to propagate all the carries introduced in this iteration - a bit forward in the next iteration - we left-shift the result of the AND operation. Just keep in mind that everything is happening in parallel. Now, what should we do with carries? We simply just sum them: the only difference is that now the task is somewhat simpler, but it’s still the same task (summing two binary numbers). We initially had two numbers: A and B. At every iteration, you XOR the two bit-strings, AND and left shift them and set A to former and B to the latter. The sum A + B remains invariant (or same) at every iteration till B becomes zero and A holds A + B (that’s when you stop). The carries will initiate a kind of chain reaction when they’re forwarded to the next bit from where one more carry goes to the next bit from that bit and so on till it finally gets resolved. Parallely, it is possible that multiple segments generate different carry chains and since a new carry means a new iteration, the iterations will continue as long as we get carries.

Finally, since the shorter chains would already have been resolved by some iteration in the past: the longest chain hence takes you farthest in the future where it ultimately gets resolved and the while loop terminates (B becomes zero as there is no carry to be forwarded now). One last thing: a carry is only propagated left, so if the rightmost carry is generated at ith bit, the positions from 0 to i - 1 currently holds the final result in A :slightly_smiling_face:

Edit: I want to add one more trivial observation. The number of carry-bits to be resolved in a single iteration (in simple words, the number of 1’s in V) is non - increasing. It may decrease or stay the same (in that case, it’ll just continue being forwarded until decreased or resolved: whatever occurs first) but it won’t increase. You can use this observation as an argument as to why the loop must terminate.

19 Likes

What are some of the corner test-cases for this problem? When I submitted the solution only the last test-case was passed. @hitch_hiker42 @melfice @alex_2oo8

What is SIGTSTP error and why I am getting it?

One of the worst cases for the problem is when the length of the bit strings differ by 1, and the carry reaction starts at the LSB and propagates through the entire length of the string (after adjustment). For example, if A = 1010101 and B = (0)101011, the length of the bit strings (after adjustment - notice the brackets in B) is 7: the first carry that’s generated at position 0 triggers a chain of carries across the entire string (notice that the XOR at every position equals 1, hence when added with an incoming carry at those positions: all of them will generate an outgoing carry to the next position). Hence the answer is: 8 (the carry generated in the ith iteration is resolved in the (i + 1)th iteration, and since every bit will generate a carry in their respective iterations (1st (technically 0th) bit in the first iteration, …, 7th bit in the seventh iteration), their resolution will take place in the iteration following those respective iterations (carry by 1st (technically 0th) bit is resolved in the second iteration, …, carry by 7th bit is resolved in the eight iteration) :slightly_smiling_face:

Ya I had looked over several test-cases when I designed the algorithm, and it is giving the right answer for the most of the test-cases including the one mentioned by you when I compared to the brute-force solution which I have written in python3

Python3 Brute-Force Solution

Python Brute-Force Solution

def binary_addition(a,b):
    loop_count = 0
    while b != 0:
        loop_count += 1
        x = a ^ b
        y = a & b
        a = x
        b = y << 1
    return loop_count

def main():
    for t in range(int(input().rstrip()):
        a = int('0b' + input().rstrip(),base = 2)
        b = int('0b' + input().rstrip(),base = 2)
        if not b:
            print("0")
        elif not a:
            print("1")
        elif a == b:
            print("2")
        else:
            print(binary_addition(a,b))

if __name__ == "__main__":
    main()
        
Solution Based on Longest Carry Sequence Concept

Solution Link: https://www.codechef.com/viewsolution/28420369

Test-Cases on which I ran my solution and got the right answer:
5
100010
0
0
100010
11100
1010
1111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111
1010101
101011
The output of my Source-Code:
0
1
3
10
8

But the Solution Based on Longest Carry Sequence Concept is not accepted by the judge. Could you tell me where the bug/logical-error is in my code? @melfice @alex_2oo8 @hitch_hiker42 @ssjgz @gainullinildar
Thanks.

1 Like

In the editorial instead of :

            if(carry > 1) {
			cur++;
		} else {
			cur = 0;
		}

the code should be
   if(carry==2) cur++;
   else cur=carry/2;

Correct me if i am wrong.

1 Like

I’ll take a while before I look at your code. I’ll do it once I get back home, I’m out at the moment. Still for reference, here’s my solution: BINADD :slightly_smiling_face:

@hitch_hiker42 No problem. Thanks :slight_smile:

Yes , i get it . Is there any pdf or writing on these topic?? Is there another algorithm for binary operation using binary operation?

@hitch_hiker42
I got what you explained , but I am unable to get how many iterations it will take to make second number 0.

If you are curious, and if you have patience and time, do read logic and propositional calculus followed by Boolean algebra and digital electronics. These two form a significant section of discrete mathematics which you need to give all that you can. If you want some quick resources, I’ll advise you to read “Discrete Mathematics” by Seymour and Lipson and first few chapters of “Digital Design” by Morris Mano. Remember, problem solving derives from all sciences :slightly_smiling_face:

1 Like

As long as there remains a carry to be resolved, the second number won’t become zero: hence the number of iterations it’ll take to make the second number zero equals the number of iterations it’ll take to resolve all carries in the binary addition :slightly_smiling_face:

1 Like

thanx for helping a poor guy, but to compute number of iterations to make the second number zero, we need to find out number of iterations it’ll take to resolve all caries in the binary addition
So we need to find this without iterating or is their any shortcut?

You need to iterate, that’s for sure. But for how long, that’s the question. :wink:

If you’re replicating the while loop given in the problem statement to find the number of iterations then it’ll give TLE. Here’s why:

Plan A (convert the bit-strings to decimal and do as given): No, you cannot pre convert the given bit-strings to regular integers in base 10 as there is no available data type to hold the intermediate results (the bit-string may be of length 105 at worst, implying a number as large as 2100000)!

Plan B (okay, so what? I’ll just apply those binary operations on the bit-strings itself): Seems like something that can be done, huh? Nope, not so fast. To find U and V in every iteration, you need to convert the individual characters (representing bits) to their integer equivalents and then apply the required operation and then convert the result back to a character to be assigned to U or V for every character in A and B. Since the ASCII conversions and binary operations (on small numbers) are constant time, you will require about n-operations (n being the length of the bigger bit-string) for this. Also, the while loop will execute about n-times so the total time is of order n2 resulting in TLE.

Plan C (the shortcut, if you consider every optimized approach as one): Make the two bit-strings of equal length (by prepending required number of zeroes to the shorter) and then compute A XOR B and A AND B in linear time and assign the results (bit-strings) to U and V respectively. Since every 1 in V indicates the start of some carry reaction and every 1 in U indicates the end of some, traverse V (from LSB to MSB: because that’s how addition is done) and when you find a 1 (because it signals the start of a carry chain): initialize a counter to 1 and continue traversing from the next position onwards in U (recall that a carry is forwarded to a higher position from where it is generated) until you reach a zero (because it signals the end of the carry chain). Keep incrementing the counter until the second loop terminates and when it does, compare if the length of this carry chain (value stored in counter) is longer than the current maximum chain: if yes, set it to the new maximum carry chain length and continue until you reach the MSB of V. The length of the longest carry chain at the end is the required answer, print it and you’re done :slightly_smiling_face:

I’ve posted my solution link above for reference but for the sake of completeness, here’s the solution function:

void solution() {
    string a, b; cin >> a >> b;
    int m = a.length(), n = b.length(), complexity(0);
    for(const char& i: b) {
        if(i == '1') {
            complexity = unit;
            break;
        }
    }
    if(m < n) {
        swap(m, n);
        swap(a, b);
    }
    string prefix(m - n, '0'), u(m, '0'), v(m, '0');
    b = prefix + b;
    for(int i = 0; i < m; i++) {
        u[i] = ((a[i] - '0') ^ (b[i] - '0')) + '0';
        v[i] = ((a[i] - '0') & (b[i] - '0')) + '0';
    }
    u = '0' + u;
    for(int i = m - 1; i >= 0; i--) {
        if(v[i] == '1') {
            int j = i, counter(unit);
            do {
                if(u[j] == '1') {
                    counter++;
                }
                else {
                    break;
                }
                j--;
            } while(j >= 0);
            counter++;
            if(counter > complexity) {
                complexity = counter;
            }
        }
    }
    cout << complexity << endl;
};
3 Likes

How’s it going.

Tried to understand solution and use the method explained. Did not work for many tries so copypasted the editorial. Still did not work. Have the test cases changed? Has this happened for anyone else?

1 Like

Finally I understood everything, I am very thankful to you. Thanks for your efforts. You just made my day. I was very curious to know the concept. Thanks a lot

1 Like

Happy to help, good luck :blush: