Implementing a wrapping addition for 32 bit integers

Questions / Help
1

In most cases Elixir and Erlang intrinsically moving to BigInt is remarkably helpful and satisfying to work with, so I know this exercise is academic. Still if I wanted to work with integers as if they were restricted to signed 32-bit integers, how would I handle overflow/wrapping?
I’m thinking the easiest way is working with integers as binaries, something like:

x = Integer.pow(2, 32) - 1
<<x:32>> # returns <<255, 255, 255, 255>>
y = 1
<<y:32>> # returns <<0, 0, 0, 1>>

If I try to do <<(x + y)::32>> I’ll get <<0, 0, 0, 0>>. What’s the best way to capture that overflow digit?

2 Likes
2

You want to capture overflow or to have wrapping addition? Because in wrapping addition 0xFFFF_FFFF + 1 == 0 not 1.

2 Likes
3

Imprecise wording on my part, sorry. I meant how do I convert <<0,0,0,0>> (or whatever the wrapped result is) back to an integer.

x = Integer.pow(2, 32) - 1
<<x:32>> # returns <<255, 255, 255, 255>>
y = 1
<<y:32>> # returns <<0, 0, 0, 1>>
z = <<(x + y)::32>> # returns <<0, 0, 0, 0>>

Is there a better way to get z into integer form without iterating over the binary as a list and reducing?

1 Like
4

If you want to treat bitstring as an unsigned-integer, and by default it will be an unsigned integer if we dont specify anything.

<<z::32>> = <<(x + y)::32>> # z = 0
<<z::32>> = <<(Integer.pow(2, 32)-1)::32>> # z = 4294967295

But from your original description, it seems like you are interested in signed integer. For that it will be

<<z::signed-integer-size(32)>> = <<(x + y)::32>> # z = 0
<<z::signed-integer-size(32)>> = <<(Integer.pow(2, 32)-1)::32>> # z = -1
2 Likes
5

Bitwise.band/2

6

maybe with binary:decode_unsigned

7

Earlier I was on mobile, now I can expand.

Addition of two N-bit integers can result with at most (N+1)-bit integer. So as we are adding 32-bit integers then we will end with at most 33-bit result. That will give us the knowledge to achieve what we want:

defmodule Carry do
  @u32_max 2 ** 32 - 1

  import Bitwise

  def add_u32(a, b) do
    r = a + b
    {r &&& @u32_max, (r >>> 32) == 1}
  end
end

a = 0xFFFF_FFFF
b = 1

{result, carry} = Carry.add_u32(a, b)

IO.puts("#{a} + #{b} = #{result} (carried? #{carry})")
#=> 4294967295 + 1 = 0 (carried? true)
5 Likes