Going below zero in unsigned integer operations

Question

I want to deduce a list of 16-bit unsigned integers from another list of 16-bit unsigned integers.

For example, given the list:

10000, 12349, 32333, 3342

and I know the first integer of the other list is 0, now I want to deduce the rest. The mapping is to subtract 10000 from them, I got

0, 2349, 22333, 58878

where 58878 = (3342-10000+65536) modulo 65536 as the result of a wrapping.

The pseudocode is something like：

 void deduce(u_int16_t list1[100], u_int16_t *list2[100], u_int16_t first)
 {
      int diff = first - list1[0];
      for (i = 0; i < 100; i++)
          (*list2)[i] = (list1[i] + diff + 65536) % 65536;
 }

but we know that there is no minus number in unsigned integers.

so how to do the mapping(or deduction)?

thanks!

Answer 1

unsigned integers variables can be subtracted more than they contain - if I understand correctly the question.

u_int16_t u = 10;
u -= 20; // => u = u - 20;
printf("%x, %u\n", u, u); // => fff6, 65526

The difference is

• when displayed, u does not show a negative value - ie the MSb (most significant bit, ie bit 15) is interpreted (here) as 2¹⁵, the next as 2¹⁴ etc...
• when extended (eg to 32 bits) the MBb is not propagated from bit 16 to bit 31 (as they would be if signed) - they're 0
• when right shifted the value MSb is always 0 (would be the same as previous MSb if signed, e.g 1 for a negative value)

So your mapping will keep working with u_int16_t (and you don't need the % modulo 65536 if you work with that type everywhere since anyway the values are on 16 bits - the modulo is implicit).

Answer 2

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

void deduce(uint16_t list1[], uint16_t list2[], size_t size){
    int32_t i, first = list1[0];

    for(i=0;i<size;++i){
    //  list2[i]= list1[i] - first;
        int32_t wk = list1[i];
        wk -= first;
        if(wk<0)
            wk += 65536;
        list2[i] = wk;
    }
}

int main(void){
    uint16_t list1[100] = {
        10000,
        12349,
        32333,
         3342
    };
    uint16_t list2[100];
    int i;

    deduce(list1, list2, 4);
    for(i = 0; i<4; ++i)
        printf("%5" PRIu16 "\n", list2[i]);

    return 0;
}

Answer 3

I'm not quite understand your question, but if what you want is to subtract every element of the first list by the different between the first element of both list. This code should work.

void deduce(uint16_t list1[], uint16_t list2[], int size)
{
    uint16_t diff = list1[0] - list2[0];
    int i;
    for (i=0; i<size; i++)
        list2[i] = list1[i] - diff;
}

You don't need to pass list2 as u_int16_t* list2[] because you actually can edit the content of the array with u_int16_t list2[]. Only use u_int16_t* list2[] if you want to do dynamic memory allocation in this function.