#Adding signed to unsigned

1 messages · Page 1 of 1 (latest)

narrow nymph
#

Given this code, assuming that a is unsigned and b is signed

a += b;

How do I make it work ? I thought about doing this but it seems a little bit overkill

if (b >= 0) {
    a += @intCast(isize, b);
} else {
    a -= abs(b);
}
boreal gyro
#

are there any constraints on the values of a and b, or could they both be anything provided the result fits in a's type?

narrow nymph
#

b can be signed

boreal gyro
#

yeah i know, i mean are there any further constraints not documented in the types

narrow nymph
#

The result should be unsigned

boreal gyro
#

assuming they're usize and isize respectively, and you just want unchecked wrapping overflow behaviour, you could do a +%= @bitCast(usize, b) - might seem a bit weird but that's sorta intentional, the point is that potential overflows are explicit

narrow nymph
#

But what if b is less than 0 ?

boreal gyro
#

two's complement means that it works

#

it's why in all major cpu architectures there aren't separate instructions for signed and unsigned addition; two's complement is kinda magic and just lets you treat everything as unsigned and provided you have wrapping overflow semantics it just works

boreal gyro
narrow nymph
#

I'm not sure to understand, in your examples @bitCast would give me a usize, so how could it be negative

boreal gyro
#

Two's complement is the encoding for signed integers used by basically every architecture for decades - it basically represents negative values as wrapping backwards from 0 (so @as(i32, -1) is represented as 0xFFFF_FFFF). It's designed in such a way that adding the underlying values as unsigned integers actually gives you back the correct result (e.g. 0xFFFFFFFF + 0xFFFFFFFF = 0xFFFFFFFE, which corresponds to -2). @bitCast here gives you that underlying representation, so for instance -1 becomes 0xFFFFFFFF, and +%= is wrapping arithmetic, which basically means you have the wrapping semantics that make explicit two's complement work

#

As a simple example of 2 + -1, we have that @bitCast(usize, -1) == 0xFFFFFFFF, and 2 == 0x00000002, and adding those values together with wrapping arithmetic gives us 0x00000001 == 1

narrow nymph
#

Does that mean that in theory, using bitwise operators, I could encode a negative number in an unsigned type ?

boreal gyro
#

Yup! There's mostly nothing special on a hardware level about signed integers (some operations do work differently, but simple addition and subtraction work exactly the same); we just make the distinction in higher-level languages because it's useful

#

CPUs don't really know what a "signed integer" is, they just know about certain signed operations (such as signed multiplication imul on x86), which just act on a Piece Of Data which the instruction assumes represents a signed integer in two's complement

narrow nymph
#

I thought that unsigned ints had double the size over signed ones. Like i8 would be from -128 to 128, and u8, from 0 to 255

boreal gyro
#

Those ranges are almost correct (i8 goes from -128 to 127, the positive range is one smaller), but that's not double the size! The amount of values representable is 256 in both cases

narrow nymph
#

Yes

#

I meant double in the positives

boreal gyro
#

Yes, that's correct then (aside from the off-by-one)

#

Signed integers (encoded using two's complement; note that there are different encodings, but nothing uses them anymore, Zig guarantees two's complement) just say that the upper half of values actually represent the negative numbers

#

so 0xFF as a u8 represents the value 255, but as an i8 represents the value -1

narrow nymph
#

But then, how could signed ints go as far as 255 and also support negatives ?

boreal gyro
#

They don't - the values from 128-255 represent negative values

#

The key thing here isn't about storing different data, but in how that data is interpreted

#

The 8-bit value 0xFF by itself isn't capable of telling us whether that represents 255 or -1; we need to know how to interpret that. Most contemporary high-level languages do that by drawing a distinction between "unsigned types", where we'd say that byte represents 255, and "signed types", where we'd say that byte represents -1

narrow nymph
#

But then how do we get a negative with our usize

#

I'm sorry if I missed something

boreal gyro
#

As far as the language is concerned, we don't - if you tried to print the value @bitCast(usize, b) for a negative b, the language would just print some stupidly large value. But because @bitCast by definition doesn't change the underlying bits, we're able to use +%= to exploit two's complement's wrapping behaviour to get the correct value

narrow nymph
#

How does +%= know that we don't want the stupidly large value ?

#

So to what I understand is that +%= treats the int as a negative value ?

#

I mean

#

A signed int

#

Sorry

boreal gyro
# narrow nymph How does `+%=` know that we don't want the stupidly large value ?

It doesn't know that, but assuming your values are within the range you want (i.e. the answer you'd get would be positive) you'll get the right answer out of the other end because of the wraparound. I should have explained this bit: the way binary addition usually works is that if you'd get a value bigger than you can store, the top bit is just chopped off. That gives us wraparound behaviour; in the 8-bit land, 0xFF + 0x01 wants to be 0x100, but you can't store a value that big in 8 bits, so you just get 0x00 instead. Similarly, 0xFF + 0x02 gives you 0x01, 0x00 - 0x01 gives you 0xFF, etc - the values wrap around at either end to the other extreme. Two's complement is designed so that just letting this wraparound happen when you add or subtract will give you the correct answer (assuming the result is in range)

#

+% is just an arithmetic operator which guarantees you'll get this wrapping behaviour - plain old + makes overflow or underflow undefined behaviour (to allow for certain optimisations). Wrapping arithmetic operators aren't directly related to two's complement, but they can be helpful when you're directly working with it. In C, there's no direct equivalent, so if people need it (for instance if they're working directly with two's complement values, as we are here) they sometimes just assume that + gives this behaviour, which is true for most compilers, but not always.

narrow nymph
#

Ohhh I think I got it :D

#

So with this a +%= @bitCast(usize, b) we overflow a wich given how two complement works, will give us the right answer

#

Is that correct ?

boreal gyro
#

yup!

narrow nymph
#

:DDD

#

I didn't think I would take that long to understand adding integers together xD

boreal gyro
#

Now that you understand that, a word of caution: any time you're having to do weird operations like this, it's a sign that there's major potential for bad behaviours like overflow. In this case, if a = 0 and b = -1, you'll get a = 0xFFFF_FFFF_FFFF_FFFF out the other end. If you know that the values will always make sense, you won't have to worry about that, but if these values come from, for instance, user input, it's important to think about whether the error case is possible. For instance, if a + b could ever be negative, maybe you actually want a to also be signed. But if they're coming from some implementation detail - for instance, it's a memory address and offset - you might be okay, but it's still important to think about where the values are coming from and whether there's any way you could break it

narrow nymph
#

Imagining that was 8 bits integers, what confused me was how could this possibly work with -128 to 255

narrow nymph
#

Sorry for taking that long to understand x)

boreal gyro
#

No worries, arithmetic on different types can be surprisingly difficult to think through

eager pecan
#

t'is a rite of passage to be confused, and then to understand two's complement shenanigans

boreal gyro
#

If coming from something like a C background it's easy to get frustrated at Zig's arithmetic rules, but C is actually dangerously permissive here, letting error cases happen silently and giving you garbage out the other end. Zig tries to make such error cases an explicit opt-in wherever possible

#

a += b would just work by itself in C, but would be undefined behaviour on overflow/underflow, which is a good place for subtle bugs and exploits to hide

narrow nymph
#

Maybe you could help me on another one too, it's still about adding and signed/unsigned so I think it still fits the thread
Assuming that a and b are unsigned and that a - b can produce a negative value
My solution was to cast a and b to signed int but maybe there is a better solution ?

eager pecan
#

two's complement could also help there

narrow nymph
#

So I could replace - with -% ?

#

And it would work ?

boreal gyro
#

The two's complement solution would be c = @intCast(isize, a -% b)

eager pecan
#

you can just use -% and then bitcast them to signed equivalent if I?m remembering right

#

ye

narrow nymph
#

Cool :D

eager pecan
#

because as stated before, two's complement is literally magic

narrow nymph
#

Now I see how just using the last bit as a bool to say whether it's negative or not is a bad idea x)

eager pecan
#

not the least bit of which is just the fact that it means you can have 0 and -0

boreal gyro
# narrow nymph Cool :D

That said, if you can guarantee that a and b will be in isize range in any reasonable case, it'd probably be better to instead do c = @intCast(isize, a) - @intCast(isize, b). Doing it like that means you get a panic on overflow in safe builds, which can be useful for weeding out bugs

eager pecan
#

true, if you want to try and guarantee you don't get a negative number, that would be the better option

#

but if the result is logically allowed to end up negative, using two's complement there is perfectly reasonable as well

boreal gyro
eager pecan
#

well, it depends on how you're defining the architecture of your program

#

if you are trying to guarantee it won't overflow over std.math.maxInt(isize), then sure

#

but if you want to allow the full range of unsigned integers, and also allow a signed result, then two's complement is there for that

boreal gyro
#

Yeah, it's always important to think about the possible inputs and how you'll end up interpreting the output

eager pecan
#

verily

boreal gyro
#

tl;dr simple arithmetic is a surprisingly complex thing to get right!

eager pecan
#

lmao fr fr

#

or well

#

simple arithmetic with limited bit width integers can be complex

#

it all becomes simple if you just allocate a huge enough integer

#

but that slow

#

we want fast

boreal gyro
boreal gyro
# eager pecan it all becomes simple if you just allocate a huge enough integer

also yeah, this is a good point to expand on. if you're writing something where the numbers are unbounded - say, a calculator program - you might actually want an arbitrary-sized integer type, which is commonly called a "bigint". these values are allocated dynamically (on the heap), and so can take up an unbounded amount of memory for bigger and bigger numbers. zig has a bigint implementation in the standard library, under std.math.big.int - you can take a look if you're interested

#

some very high-level languages (most notably python) use bigints by default, meaning you can represent arbitrary quantities with no problem