Adding bits, simpler

Question

Considering that two bitsets are provided in the form of strings, char a[] and char b[], as in the code below. And the task of add that bitsets is given. I take it and wrote the following to sum the two bitsets:

#include <stdio.h>
#include <string.h>
int carry = 0;
char result(char r, int c) {
 char R = '0';
 if (carry) {
 if (c) {
 R = '0';
 carry = 1;
 } else {
 R = r == '0' ? '1' : '0';
 carry = R == '0' ? 1 : 0;
 }
 } else {
 if (c) {
 R = '0';
 carry = 1;
 } else {
 R = r;
 carry = 0;
 }
 }
 return R;
}
char sum(int x, int y) {
 char r = '0';
 if (x ^ y) 
 r = result('1', 0);
 else if (x & y)
 r = result('0', 1);
 else 
 r = result('0', 0);
 return r;
}
int main() { 
 char a[] = "01";
 char b[] = "01";
 char c[] = "00";
 for (int i = strlen(c)-1; i > -1; i--) 
 c[i] = sum(a[i] == '0' ? 0 : 1, b[i] == '0' ? 0 : 1);
 printf("%s\n", c);
}

Is it possible to make it simpler?

• JS1: Are a and b guaranteed to be the same length? What about if the top bit carries? Should c be extended by 1 character?
• KcFnMi: An answer even without that level of sophistication will be appreciated.
• Cody Gray: I find the code very difficult to follow, mainly because of the poor (nondescript) naming choices, but also because of the lack of a clear explanation of what problem it is supposed to be solving (either in comments or in the body of the question). That's kind of my pseudo-review; I don't have the time or desire to think much harder about what it's supposed to be doing. In other words—I'd hand this back for a revision straight-away, but I don't think that makes a suitable answer here.

Answer 1

OP's approach is very tangled.

No provisions are made for a final carry-out of the sum.

char result(char r, int c) { should at least been used description names: char add_digit_carry(char digit, int carry) {

for (int i = strlen(c)-1; i > -1; i--) --> Little things like i >= 0; are certainly easier to follow.

strlen() returns type size_t. Array indexing and sizing is best done with that type.

---

The basic way to add strings is just like grade-school math: add the 1 places, form the sum and carry. Then add the next most significant column along with the carry. Repeat for all digits and consider a carry out.

Assuming memory issues are not a big concern ....

#include <assert.h>
#include <stdlib.h>
#include <string.h>
// c = a + b
char *KFM_add(char *c, size_t c_size, const char *a, const char *b, int base) {
 assert(base >= 2 && base <= 10 && c_size > 0);
 size_t a_end = strlen(a);
 size_t b_end = strlen(b);
 size_t c_end = c_size - 1;
 c[c_end] = '0円';
 int carry = 0;
 while (a_end > 0 || b_end > 0 || carry > 0) {
 int sum = carry;
 if (a_end > 0) {
 sum += a[--a_end] - '0';
 }
 if (b_end > 0) {
 sum += b[--b_end] - '0';
 }
 assert(c_end > 0);
 c[--c_end] = sum % base + '0';
 carry = sum / base;
 }
 // return memmove(&c[0], &c[c_end], c_end); // Corrected code @JS1
 return memmove(&c[0], &c[c_end], c_size - c_end);
}
#include <stdio.h>
int main(void) {
 char a[] = "111";
 char b[] = "01";
 char c[80];
 puts(KFM_add(c, sizeof c, a, b, 2)); // Output 1000
}

Should one want to explore binary addition closer:

#include <stdbool.h>
 ...
 bool carry = 0;
 while (a_end > 0 || b_end > 0 || carry > 0) {
 bool a_bit = (a_end > 0) ? (a[--a_end] - '0') : false;
 bool b_bit = (b_end > 0) ? (b[--b_end] - '0') : false;
 assert(c_end > 0);
 c[--c_end] = (a_bit ^ b_bit ^ carry) + '0';
 carry = (a_bit & b_bit) | (b_bit & carry) | (carry & a_bit);
 }
 ...

• KcFnMi: What's the meaning of F, K and M in FKM_add?
• chux: @KcFnMi FKM is a shorted form of KcFnMi, that was inadvertently re-ordered..