Adding two n and m bit binary numbers

Question

Recently I was studying bitwise operators and bit-manipulation algorithms and I found out an algorithm to add two binary numbers.

Pseudocode is as follows:

function add(A, B):
 while B is greater than 0:
 U = A XOR B, where XOR = Bitwise XOR of A and B.
 V = A AND B, where AND = Bitwise AND of A and B.
 A = U
 B = V * 2, this instruction is equivalent to V << 1
 return A

A and B are bit strings of length N and M where the limits for N and M are: 0 < N <= 10^5 and 0 < M <= 10^5. Both the bit strings can be of different lengths.

I was wondering about finding out how many times the while loop runs before the B = 0.

Problem Statement:

How many times does the while loop run before B = 0?

I wrote an algorithm in C which takes two strings A and B as input. If the length of both the strings is not same then first make them same, then perform bitwise XOR and bitwise AND and bitwise left-shift to implement multiplication by 2 as described in the above algorithm.

Source code is as follows:

#include<stdio.h>
#include<stdlib.h>
#include<inttypes.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>
#define STRING_LENGTH_MAX 100001
static const uint64_t binary_to_decimal(char[*]);
static const uint64_t binary_exponentiation(uint64_t,uint64_t);
static const uint32_t binary_addition_integers(uint64_t,uint64_t);
static char* make_string_equal(char[*],uint32_t);
static const bool check_all_zeroes(char[*]);
static const uint32_t binary_addition_strings(char[*],char[*]);
static char* bitwise_xor_strings(char[*],char[*]);
static char* bitwise_and_strings(char[*],char[*]);
static char* bitwise_left_shift_by_one_strings(char[*]);
int main(void) {
 int32_t test;
 printf("Enter the number of test-cases\n");
 scanf("%"SCNd32, &test);
 assert(test > 0 && test < 100001);
 while(test--) {
 char *binary_string_A = calloc(STRING_LENGTH_MAX,sizeof(char));
 char *binary_string_B = calloc(STRING_LENGTH_MAX,sizeof(char));
 printf("Enter the bit-strings A and B\n");
 scanf("%s%s", binary_string_A,binary_string_B);
 uint32_t len_binary_string_A = strlen(binary_string_A);
 uint32_t len_binary_string_B = strlen(binary_string_B);
 uint32_t loop_count = 0;
 if(len_binary_string_A < 63 && len_binary_string_B < 63) {
 uint64_t a = binary_to_decimal(binary_string_A);
 uint64_t b = binary_to_decimal(binary_string_B);
 if(!b) {
 loop_count = 0;
 } else if(!a) {
 loop_count = 1;
 } else if(a == b) {
 loop_count = 2;
 } else {
 loop_count = binary_addition_integers(a,b);
 }
 } else {
 if(len_binary_string_A < len_binary_string_B) {
 binary_string_A = make_string_equal(binary_string_A,len_binary_string_B);
 if(!binary_string_A) {
 fprintf(stderr,"Line number: %u: Not able to allocate the memory to *binary_string_A\n", __LINE__);
 return EXIT_FAILURE;
 }
 } else {
 binary_string_B = make_string_equal(binary_string_B,len_binary_string_A);
 if(!binary_string_B) {
 fprintf(stderr,"Line number: %u: Not able to allocate memory to *binary_string_B\n", __LINE__);
 return EXIT_FAILURE;
 }
 }
 if(check_all_zeroes(binary_string_B)) {
 loop_count = 0;
 } else if(check_all_zeroes(binary_string_A)) {
 loop_count = 1;
 } else if(!strncmp(binary_string_A,binary_string_B,strlen(binary_string_A))) {
 loop_count = 2;
 } else {
 loop_count = binary_addition_strings(binary_string_A,binary_string_B);
 }
 }
 free(binary_string_A);
 free(binary_string_B);
 printf("Loop-Runs: %"PRIu32"\n", loop_count);
 }
 return EXIT_SUCCESS;
}
static const uint64_t binary_to_decimal(char binary_string[]) {
 uint32_t string_len = strlen(binary_string);
 uint64_t decimal_value = 0;
 for(int8_t i = (string_len - 1), power = 0; i >= 0; --i,++power) {
 if(!(binary_string[i] == '0')) {
 if(i == (string_len - 1)) {
 decimal_value += binary_string[i] - '0';
 } else {
 decimal_value += (binary_string[i] - '0') * binary_exponentiation(2,power);
 }
 }
 }
 return decimal_value;
}
static const uint64_t binary_exponentiation(uint64_t base,uint64_t expo) {
 uint64_t result = 1;
 if(!expo) {
 return result;
 } else if(expo == 1) {
 return base;
 } else {
 while(expo) {
 if(expo & 1) {
 result *= base;
 }
 base *= base;
 expo >>= 1;
 }
 }
 return result;
}
static const uint32_t binary_addition_integers(uint64_t a,uint64_t b) {
 uint32_t loop_count = 0;
 while(b) {
 ++loop_count;
 uint64_t x = a ^ b;
 uint64_t y = a & b;
 a = x;
 b = y << 1;
 }
 return loop_count;
}
static char* make_string_equal(char binary_string[],uint32_t target_len) {
 uint32_t prev_len = strlen(binary_string);
 binary_string = realloc(binary_string,(sizeof(char) * (target_len + 1)));
 if(binary_string) {
 for(int32_t i = (prev_len - 1), j = (target_len - 1); i >= 0; --i,--j) {
 binary_string[j] = binary_string[i];
 }
 uint32_t limit = target_len - prev_len;
 for(uint32_t i = 0; i < limit; ++i) {
 binary_string[i] = '0';
 }
 binary_string[target_len] = '0円';
 } else {
 fprintf(stderr,"Line number: %u: Not able to re-allocate %lu bytes of memory\n", __LINE__,(sizeof(char) * target_len));
 return NULL;
 }
 return binary_string;
}
static const bool check_all_zeroes(char binary_string[]) {
 bool is_all_zeroes = true;
 for(uint32_t i = 0; binary_string[i] != '0円'; ++i) {
 if(binary_string[i] != '0') {
 is_all_zeroes = false;
 break;
 }
 }
 return is_all_zeroes;
}
static const uint32_t binary_addition_strings(char *binary_string_A,char *binary_string_B) {
 uint32_t loop_count = 0;
 while(!check_all_zeroes(binary_string_B)) {
 ++loop_count;
 char *binary_string_X = bitwise_xor_strings(binary_string_A,binary_string_B);
 char *binary_string_Y = bitwise_and_strings(binary_string_A,binary_string_B);
 binary_string_A = binary_string_X;
 binary_string_B = bitwise_left_shift_by_one_strings(binary_string_Y);
 binary_string_A = make_string_equal(binary_string_A,strlen(binary_string_B));
 }
 return loop_count;
}
static char* bitwise_xor_strings(char binary_string_A[],char binary_string_B[]) {
 uint32_t xor_result_len = strlen(binary_string_A) + 1;
 char *xor_result = calloc(xor_result_len,sizeof(char));
 if(xor_result) {
 for(int32_t i = (xor_result_len - 2); i >= 0; --i) {
 xor_result[i] = ((binary_string_A[i] - '0') ^ (binary_string_B[i] - '0')) + '0';
 }
 xor_result[xor_result_len - 1] = '0円';
 } else {
 fprintf(stderr,"Line number: %u: Not able to allocate %lu bytes of memory to *xor_result\n", __LINE__,(sizeof(char) * xor_result_len));
 xor_result = NULL;
 }
 return xor_result;
}
static char* bitwise_and_strings(char binary_string_A[],char binary_string_B[]) {
 uint32_t and_result_len = strlen(binary_string_A) + 1;
 char *and_result = calloc(and_result_len,sizeof(char));
 if(and_result) {
 for(int32_t i = (and_result_len - 2); i >= 0; --i) {
 and_result[i] = ((binary_string_A[i] - '0') & (binary_string_B[i] - '0')) + '0';
 }
 and_result[and_result_len - 1] = '0円';
 } else {
 fprintf(stderr,"Line number: %u: Not able to allocate %lu bytes of memory to *and_result\n", __LINE__,(sizeof(char) * and_result_len));
 and_result = NULL;
 }
 return and_result;
}
static char* bitwise_left_shift_by_one_strings(char binary_string[]) {
 uint32_t bitwise_left_shift_by_one_result_len = strlen(binary_string) + 2;
 char *bitwise_left_shift_by_one_result = realloc(binary_string,(sizeof(char) * bitwise_left_shift_by_one_result_len));
 if(bitwise_left_shift_by_one_result) {
 bitwise_left_shift_by_one_result[bitwise_left_shift_by_one_result_len - 2] = '0';
 bitwise_left_shift_by_one_result[bitwise_left_shift_by_one_result_len - 1] = '0円';
 } else {
 fprintf(stderr,"Line number: %u: Not able to re-allocate memory block to *bitwise_left_shift_by_one_result\n", __LINE__);
 bitwise_left_shift_by_one_result = NULL;
 }
 return bitwise_left_shift_by_one_result;
}

Program Output:

Enter the number of test-cases
4
Enter the bit-strings A and B
100010
0
Loop-Runs: 0
Enter the bit-strings A and B
0
100010
Loop-Runs: 1
Enter the bit-strings A and B
11100
1010
Loop-Runs: 3
Enter the bit-strings A and B
1111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111
Loop-Runs: 10

As you can see the algorithm which I come up with does execute all the steps in order to find out the answer i.e. loop count, but as I am only interested in how many times the loop runs and if there are any other way of finding that value.

How can I optimize the code if the number of bits in the binary numbers is> 500? What I did was if the number of bits in the given binary numbers A and B <= 63, I find their decimal equivalent and use the bitwise operators defined in C, but as you know if the length of the string becomes> 64 its decimal equivalent cannot be stored in a normal 64-bit unsigned integer in C/C++. So I just implemented the above algorithm on bit strings without finding their decimal equivalent but the algorithm which I designed is not fast enough if n> 500 so, can you tell how can I optimize my code.

However, I can use the following Python code to accomplish the task:

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():
 test = int(input())
 for t in range(test):
 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()

• David G.: I think the first usual optimization would be to do it one bit at a time, propagating the carry. This changes an O(n^2) operation into an O(n) operation. The you can group the bits into larger integer values, and if desired use the + operator, still keeping track of the carry.
• strikersps: So, can I say that the total number of times the while loop runs is equal to number of times carry is generated? In the question I need to find out how many times the while loop runs, and the above implementation takes (O(n) for XOR + O(n) for AND + O(n) for Left shift by one) * Number of times while loop executes in worst-case. Can I do better?
• David G.: If you try to add (2^n)-1 and 1, the loop will run n times. If you really want to optimize, there really is only one good solution: write in assembly. There are machine instructions specifically designed for this that aren't exposed in higher level languages. (Although if you are using python, they already have done the work for you.)
• David G.: I think the total number of loops is size of the largest chain of carrys. This actually is an issue in hardware design. There is something called (I think) a "fast carry" (that I never got the details of) that is supposed to speed up a large adder. This supplements a chain of full adders to get the result faster.
• David G.: @Suraj: At this point, maybe a reference: en.wikipedia.org/wiki/Adder_(electronics)#Full_adder

Answer 1

how can I can make my C code better & efficient.

Simplification for binary_to_decimal()

// static const uint64_t binary_to_decimal(char binary_string[]) {
static uint64_t binary_to_uint64(const char *binary_string) {
 uint64_t value = 0;
 while (*binary_string >= '0' && *binary_string <= '1') {
 value = value*2 + (*binary_string++ - '0');
 }
 return value;
}

Now binary_exponentiation() is no longer needed.

Answer 2

The static declaration of each of the functions is good, especially if the code is merged into a larger program.

Error Checking

When using any memory allocation function such as calloc(size_t number_of_items, size_t size_of_item), the return value should be checked to see if it NULL. If the function fails it returns NULL. Accessing memory through a null pointer results in unknown behavior. The program could crash or corrupt the data in the program.

While the code is performing error checking on the first scanf which reads the number of tests, the input from the second scanf is not checked. This may lead to errors in the processing of the strings.

Magic Numbers

The assert that follows the first scanf contains the number 100001. It isn't clear in the program why the maximum number of tests is 100001. There is a symbolic constant for this number defined (STRING_LENGTH_MAX) but the maximum length of the strings shouldn't have anything to do with the maximum number of test cases.

Complexity

Most of the functions are a reasonable size and complexity, but the function main() is too complex (does too much). As programs grow in size, the use of main() should be limited to calling functions that parse the command line, calling functions that set up for processing, calling functions that execute the desired function of the program, and calling functions to clean up after the main portion of the program.

There is also a programming principle called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

The contents of the while(test--) loop should be in its own function, and that function should probably be broken up into 2 or 3 functions as well.

Smaller functions are easier to write, debug, read and maintain. In some instances they may be reused as well.

Use the Native Word Size of the Processor

The native word size of the processor will provide the best performance when the code is executing. Using a smaller sized word can slow down the processing; most processors today have a word size of 64 bits, so forcing uint32_t may be counter-productive. If the variable should be unsigned, just use the type declaration unsigned; if the variable can take on negative values use int. This code doesn't need to use smaller word sizes.

The repeated use of calloc() may slow down the program. It might be better to use arrays rather than allocated memory.

Possible Program Structure

As C programs get larger, it becomes necessary to break files up by function into modules. Most of the functions in this program can be moved into another C file, with a header file providing the public interfaces. In this case, there would be one public interface called by main() which would be the execution of each test case (suggested above, but not yet written). This would remove all of the function prototypes at the top of the file.

• chux: "most processors today have a word size of 64 bits" --> Disagree, billion of processors per year now are now embedded ones, with 32 bit and smaller dominating.
• strikersps: The syntax which I used for declaring functions are correct and my program gets successfully compiled through gcc compiler and executes as intended on Ubuntu Linux 18.04 LTS. Actually I have read in a reddit post that [*] syntax is used for the declaration of Variable Length Arrays when passing into function.
• Lundin: "There are a number of syntax errors if you are using a strict C compiler; the following function prototypes don't compile using a compiler that really follows the C programming standard" This is completely wrong. If you don't know the standard well, you should compile with strict settings before making such claims. It's clear that you aren't aware of the exotic [*] syntax that's been standard for 20 years. It declares an array parameter of incomplete type, that has to be completed upon function definition. Completely useless feature but perfectly valid C.
• pacmaninbw: @larkey I have removed the [*] syntax section.
• Lundin: It would be valid to remark about using qualifiers on return types though, since that doesn't make any sense.

Answer 3

First of all, thanks to all the answers, I learned something new from all those answers.

Now coming back to the problem-statement, as no answer gave me an exact way of solving the problem in an efficient manner, so I did some research about the way the binary addition is performed, and I found that the algorithm described is known as No-Carry Adder in digital-logic, and the name is because there is no carry generated in the process.

Algorithm for No Carry Adder:

function no_carry_adder(A,B)
 while B != 0:
 X = A XOR B, Bitwise-XOR of A,B.
 Y = A AND B, Bitwise-AND of A,B.
 A = X
 B = Y << 1, Multiplying Y by 2.
 return A

As you can see, the while loop executes those four instructions again and again until B = 0, and when B = 0, binary number stored in A is the answer. Now the question was to find out how many times the while loop will execute before B = 0 or B becomes zero.

If I have gone for the naive way i.e write the algorithm as it is described in any programming language like in Python it will give me an answer but it will be time-consuming if the number of bits in the binary string A and B is > 500.

So when you analyze some of cases, for example:

• Case 1: When both A = B = 0.
  In this case the number of times the loop iterates = 0 as B = 0.
• Case 2: When A != 0 and B = 0.
  In this case the number of times the loop iterates = 0 as B = 0.
• Case 3: When A = 0 and B != 0.
  In this case, the number of times the loop iterates = 1 because after the first iteration, the value of X = B as when you do the bitwise XOR of any binary number with 0 the result is the number itself. The value of Y = 0 because bitwise AND of any number with 0 is 0. So, you can see Y = 0 then B = 0 as Y << 1 = 0.
• Case 4: When A = B and A != 0 and B != 0.
  In this case, the number of times the loop iterates = 2 because in first iteration the value A = 0, why because bitwise XOR of two same numbers is always 0 and value of Y = B because bitwise AND of two same numbers is the number itself and then B = Y << 1, after the first iteration, this case becomes Case-3. So, the number of iteration will always be 2.
• Case-5: When A != B and A != 0 and B != 0.
  In this case, the number of times the loop iterates = length of the longest carry-chain.

Algorithm to calculate the longest carry-chain:

• First make both the binary strings A and B of equal length if they are not of equal length.

• As we know the length of the largest carry sequence will be the answer, I just need to find the maximum carry sequence length I have occurred till now.

• I will iterate from left to right i.e. LSB to MSB and:

  • if carry + A[i] + B[i] == 2 means that bit marks the start of carry-sequence, so ++curr_carry_sequence and carry = 1.
  • if carry + A[i] + B[i] == 3 means the carry which was forwarded by previous bit addition is consumed here and this bit will generate the new carry and length of carry-sequence will reset to 1 i.e. curr_carry_sequence = 1 and carry = 1.
  • if carry + A[i] + B[i] == 1 or 0 means carry generated by the previous bit resolves here and it will mark the end of the carry-sequence, so the length of the sequence will reset to 0. i.e. curr_carry_sequence = 0 and carry = 0.

• Now if curr_carry_seq length is > than max_carry_sequence, then you update the max_carry_sequence.

• Answer would be max_carry_sequence + 1.

Solution source-code in C

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>
#define MAX_STRING_LENGTH 100001
static int compute_loop_iteration(const char *const, const char *const);
static bool check_all_zeroes(const char *const);
int main(void) {
 int test;
 scanf("%d", &test);
 assert(test > 0 && test < 100001);
 while(test--) {
 char a[MAX_STRING_LENGTH],b[MAX_STRING_LENGTH];
 scanf("%s%s", a,b);
 const size_t len_a = strlen(a), len_b = strlen(b);
 char *binary_string_A, *binary_string_B;
 binary_string_A = binary_string_B = NULL;
 if(len_a < len_b) {
 binary_string_A = calloc((len_b + 1), sizeof(char));
 memset(binary_string_A, '0', (sizeof(char) * (len_b - len_a)));
 memmove(&binary_string_A[len_b - len_a], a, (sizeof(char) * len_a));
 binary_string_B = calloc((len_b + 1), sizeof(char));
 snprintf(binary_string_B,len_b + 1, "%s", b);
 } else if(len_a > len_b) {
 binary_string_B = calloc((len_a + 1), sizeof(char));
 memset(binary_string_B, '0', (sizeof(char) * (len_a - len_b)));
 memmove(&binary_string_B[len_a - len_b], b, (sizeof(char) * len_b));
 binary_string_A = calloc((len_a + 1), sizeof(char));
 snprintf(binary_string_A,len_a + 1, "%s", a);
 } else {
 binary_string_A = calloc((len_a + 1), sizeof(char));
 snprintf(binary_string_A,(len_a + 1), "%s", a);
 binary_string_B = calloc((len_b + 1), sizeof(char));
 snprintf(binary_string_B,(len_b + 1), "%s", b);
 }
 int loop_count = 0;
 if(check_all_zeroes(binary_string_B)) {
 loop_count = 0;
 } else if(check_all_zeroes(binary_string_A)) {
 loop_count = 1;
 } else if(!strcmp(binary_string_A,binary_string_B)) {
 loop_count = 2;
 } else {
 loop_count = compute_loop_iteration(binary_string_A, binary_string_B);
 }
 printf("%u\n", loop_count);
 free(binary_string_A);
 free(binary_string_B);
 }
 return EXIT_SUCCESS;
}
static bool check_all_zeroes(const char *const binary_string) {
 bool is_zeroes = true;
 for(unsigned int i = 0; '0円' != binary_string[i]; ++i) {
 if('0' != binary_string[i]) {
 is_zeroes = false;
 break;
 }
 }
 return is_zeroes;
}
static int compute_loop_iteration(const char *const binary_string_A, const char *const binary_string_B) {
 const size_t limit = strlen(binary_string_A);
 int carry, current_carry_seq_len, max_carry_seq_len;
 carry = current_carry_seq_len = max_carry_seq_len = 0;
 for(int i = limit - 1; i >= 0; --i) {
 carry += (binary_string_A[i] - '0') + (binary_string_B[i] - '0');
 switch(carry) {
 case 3:
 current_carry_seq_len = 1;
 carry -= 2;
 break;
 case 2:
 --carry;
 ++current_carry_seq_len;
 break;
 default:
 carry = current_carry_seq_len = 0;
 break;
 }
 if (current_carry_seq_len > max_carry_seq_len) {
 max_carry_seq_len = current_carry_seq_len;
 }
 }
 return max_carry_seq_len + 1;
}