0
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ Are a and b guaranteed to be the same length? What about if the top bit carries? Should c be extended by 1 character? \$\endgroup\$ – JS1 Dec 28 '16 at 21:33
  • \$\begingroup\$ An answer even without that level of sophistication will be appreciated. \$\endgroup\$ – KcFnMi Dec 28 '16 at 21:58
  • \$\begingroup\$ 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. \$\endgroup\$ – Cody Gray Dec 30 '16 at 9:54
2
\$\begingroup\$

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);
  }
  ...
\$\endgroup\$
  • 1
    \$\begingroup\$ What's the meaning of F, K and M in FKM_add? \$\endgroup\$ – KcFnMi Dec 29 '16 at 11:06
  • 1
    \$\begingroup\$ @KcFnMi FKM is a shorted form of KcFnMi, that was inadvertently re-ordered.. \$\endgroup\$ – chux Dec 29 '16 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.