stevensonmt
Implementing a wrapping addition for 32 bit integers
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?
Marked As Solved
hauleth
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)
Also Liked
hauleth
You want to capture overflow or to have wrapping addition? Because in wrapping addition 0xFFFF_FFFF + 1 == 0 not 1.
akash-akya
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
stevensonmt
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?
Popular in Questions
Other popular topics
Latest on Elixir Forum
Sponsor Spotlight
Enabling companies to succeed by building software people love.
Categories:
Sub Categories:
Forums
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Develop your skills with books, videos, and courses.
Producing high quality Elixir screencasts since 2017.
The deployment platform built for Elixir: PaaS ease, VPS control.
Courses that'll move you from confusion to "Aha, now I get it!"