Overflow when adding unsigned int with unsigned int

Question

I am trying to find a solution for this one (codewars cata, 6 kyu):

Create a function that returns the sum of the two lowest positive numbers given an array of minimum 4 positive integers. No floats or non-positive integers will be passed. For example, when an array is passed like [19, 5, 42, 2, 77], the output should be 7. [10, 343445353, 3453445, 3453545353453] should return 3453455.

And i've almost found it. But obviously i have some misunderstanding about types mechanics here. For the test case

numbers = {2000000000, 2000000000, 2000000000, 2000000000, 2000000000}

I obtain overflow. And this is totally strange for me. I've read that in C int type size depends on compiling system. I have 64bit system, so my int is very large. Moreover, in this task we have only unsigned integers, so it seems that 32 bits <-> 4*10^9 could be enough. I've tried to use uint_32t and uint_64t types. Right now i am trying to cast all variables i have and this is not handy way. What else i need to understand to find the solution?

Here is my current code:

#include <stddef.h>
#include <stdio.h>
long sum_two_smallest_numbers(size_t n, const int numbers[n]) {
  int current_low1;//suppose first 2 ones are the lowest
  int current_low2;//and current_low1 is reserved for the lowest one

  int delta1;//variables for comparations
  int delta2;
  //every new value in array to be compared with 
  //current_low1 and current_low2.
  //then define - if new values are lesser
  //and if so - find out is new value the lowest
  if (numbers[0] < numbers[1]){
    current_low1 = numbers[0];
    current_low2 = numbers[1];
  } else {
    current_low1 = numbers[1];
    current_low2 = numbers[0];
  }
  int ind;
  for (ind = 2; (unsigned long) ind < n; ind++){
    if ((numbers[ind] < current_low1) && (numbers[ind] < current_low2)){
      delta1 = current_low1 - numbers[ind];
      delta2 = current_low2 - numbers[ind];
      if (delta1 > delta2){
        current_low1 = numbers[ind];
      } else{
        current_low2 = numbers[ind];
      }
    } else if ((numbers[ind] >= current_low1) && (numbers[ind] < current_low2)){
      current_low2 = numbers[ind];
    } else if ((numbers[ind] < current_low1) && (numbers[ind] >= current_low2)){
      current_low1 = numbers[ind];
    }
    }

  return (unsigned long)(current_low1 + current_low2);
}

Many thanks for your answers. I've found the solution after reading all your posts and after some pondering... So, i've used signed integers. Because the int declaration invoke signed integer by default. Then i've changed the first 4 variable's declarations to unsigned int. And now it works! I do not even need anymore to typacast the return sentence to long.

Thanks to you all, especially @Adrian Mole!

You could use long long for the function type and cast the values before adding. If your long is 64-bits you still need to cast before addition to prevent overflow. return (long)current_low1 + current_low2;. Your cast is done after the sum has already overflowed. — Weather Vane
– Weather Vane, Commented Oct 26, 2020 at 17:38
"I have 64bit system, so my int is very large." - Do you know this or just assume it? int is guaranteed to be at least 16 bits, but it's NOT guaranteed to be bigger under any circumstances. — klutt
– klutt, Commented Oct 26, 2020 at 17:43
Just print sizeof(int) to be sure. If your int is 64-bits, why does the function need to use long? — Weather Vane
– Weather Vane, Commented Oct 26, 2020 at 17:44
Try int, long, unsigned long with unsigned long long. Replace int ind; with size_t ind; — chux
– chux, Commented Oct 26, 2020 at 17:53
7race, "such conditions could not be sufficient is overwhelming for me. " --> that is how int feels with 2000000000 + 2000000000, overwhelmed 😉 — chux
– chux, Commented Oct 26, 2020 at 18:07

jacob galam · Accepted Answer · 2020-10-26 18:01:31Z

2

I change the types to uint64_t and call it.

#include <stddef.h>
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

uint64_t sum_two_smallest_numbers(size_t n, const uint64_t  numbers[n]) {
  uint64_t  current_low1;//suppose first 2 ones are the lowest
  uint64_t  current_low2;//and current_low1 is reserved for the lowest one

  uint64_t  delta1;//variables for comparations
  uint64_t  delta2;
  //every new value in array to be compared with 
  //current_low1 and current_low2.
  //then define - if new values are lesser
  //and if so - find out is new value the lowest
  if (numbers[0] < numbers[1]){
    current_low1 = numbers[0];
    current_low2 = numbers[1];
  } else {
    current_low1 = numbers[1];
    current_low2 = numbers[0];
  }
  size_t ind;
  for (ind = 2; ind < n; ind++){
    if ((numbers[ind] < current_low1) && (numbers[ind] < current_low2)){
      delta1 = current_low1 - numbers[ind];
      delta2 = current_low2 - numbers[ind];
      if (delta1 > delta2){
        current_low1 = numbers[ind];
      } else{
        current_low2 = numbers[ind];
      }
    } else if ((numbers[ind] >= current_low1) && (numbers[ind] < current_low2)){
      current_low2 = numbers[ind];
    } else if ((numbers[ind] < current_low1) && (numbers[ind] >= current_low2)){
      current_low1 = numbers[ind];
    }
    }

  return (current_low1 + current_low2);
}

#define SIZE 5

int main()
{
    
    uint64_t  balance[SIZE] = {2000000000, 2000000000, 2000000000, 2000000000, 2000000000};

    printf("%" PRIu64, sum_two_smallest_numbers(SIZE, balance));

    return 0;
}

It print 4000000000

printf("%" PRIu64... and #include <inttypes.h> it for printing uint64_t

edited Oct 26, 2020 at 18:01

answered Oct 26, 2020 at 17:46

jacob galam

8111 gold badge10 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

jacob galam Over a year ago

@chux-ReinstateMonica I meant to return uint64_t but this is still words for some reason

jacob galam Over a year ago

@chux-ReinstateMonica ind need to be size_t because it index, right, right?

chux Over a year ago

As you had coded, uint64_t ind works when size_t is not wider. Yet with that code, ind could be unnecessarily wider. Best to match types. As n was size_t, the index ind does not need a wder type and could fail if ind was narrower. Use size_t for array indexing and sizing.

chux Over a year ago

Should you want more robustness: consider what happens when n < 2.

Adrian Mole · Accepted Answer · 2020-10-26 17:46:21Z

1

Don't assume, just because your operating system or platform is 64-bits, that your C compiler has a 64-bit int type. In fact, many/most such systems (e.g. MSVC on 64-bit Windows) do not.

If your base int type is 32-bits, then the sum of two 2000000000 signed integers will overflow (but unsigned should not).

So, declare your numbers argument as const int64_t numbers[n]; and, similarly, use that int64_t type in the declaration of the array in the calling module. You can probably also use long long int, as this should also be at least 64 bits wide.

You should also change the relevant local int variables in the sum_two_smallest_numbers function (and that function's return type) to 'explicit' 64-bit (or long long) integers.

answered Oct 26, 2020 at 17:46

Adrian Mole

52.1k193 gold badges61 silver badges101 bronze badges

4 Comments

7race Over a year ago

Thanks for advice. But you are telling that "unsigned should not". So, how overflow is even possible in my situation?

12431234123412341234123 Over a year ago

Why int64_t and not uint64_t?

Adrian Mole Over a year ago

@7race For 32-bit integers, the maximum value for signed int is 2147483647 and the maximum for unsigned int is 4294967295. The latter will allow the addition of two 2000000000 but the former will not.

Adrian Mole Over a year ago

@12431234123412341234123 The OP's code uses signed integers, so I stuck with those.

Collectives™ on Stack Overflow

Overflow when adding unsigned int with unsigned int

2 Answers 2

4 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related