135 lines
3.9 KiB
Rust
135 lines
3.9 KiB
Rust
use core::ops::Add;
|
|
use std::cmp::Ordering;
|
|
|
|
#[derive(Debug, Clone)]
|
|
pub struct BigInt{
|
|
digits : Vec<u32>
|
|
}
|
|
|
|
impl From<String> for BigInt {
|
|
fn from(bitstring: String) -> Self {
|
|
let length = bitstring.len();
|
|
let start = length % 32;
|
|
let mut digits : Vec<u32> = (start..length).step_by(32).rev().map(
|
|
|i| u32::from_str_radix(&bitstring[i..i+32], 2).unwrap()
|
|
).collect();
|
|
|
|
match u32::from_str_radix(&bitstring[..start], 2){
|
|
Ok(x) => digits.push(x),
|
|
Err(_) => {}
|
|
};
|
|
|
|
Self{
|
|
digits: digits
|
|
}
|
|
}
|
|
}
|
|
|
|
impl From<BigInt> for String{
|
|
fn from(bint: BigInt) -> String{
|
|
let x = bint.digits.iter().map(|x| format!("{:032b}", x)).rev().collect::<String>();
|
|
match x.trim_start_matches('0'){
|
|
"" => "0".to_string(),
|
|
y => y.to_string()
|
|
}
|
|
}
|
|
}
|
|
|
|
impl BigInt{
|
|
pub fn len(&self) -> usize{
|
|
self.digits.len()
|
|
}
|
|
}
|
|
|
|
impl Add for BigInt {
|
|
type Output = Self;
|
|
|
|
fn add(self, other: Self) -> Self{
|
|
let (len1, len2) = (self.len(), other.len());
|
|
let digits = match len1.cmp(&len2){
|
|
Ordering::Equal => {
|
|
let mut digits = vec![0; len1 + 1];
|
|
let mut rem = 0;
|
|
for (idx, (d1, d2)) in self.digits.into_iter().zip(other.digits.into_iter()).enumerate(){
|
|
let mut sum = d1 + d2 + rem;
|
|
if u32::MAX - d1 < d2 + rem {
|
|
rem = 1;
|
|
} else {
|
|
rem = 0;
|
|
}
|
|
digits[idx] = sum;
|
|
}
|
|
if rem == 0 {
|
|
digits.pop();
|
|
}
|
|
digits
|
|
},
|
|
Ordering::Less => {
|
|
let mut digits = vec![0; len2 + 1];
|
|
let mut rem = 0;
|
|
for (idx, (d1, d2)) in self.digits.iter().zip(other.digits.iter()).enumerate(){
|
|
let mut sum = d1 + d2 + rem;
|
|
if u32::MAX - d1 < d2 + rem {
|
|
rem = 1;
|
|
} else {
|
|
rem = 0;
|
|
}
|
|
digits[idx] = sum;
|
|
}
|
|
for idx in len1..len2{
|
|
let sum = other.digits[idx] + rem;
|
|
digits[idx] = sum;
|
|
if u32::MAX - other.digits[idx] < rem{
|
|
rem = 1;
|
|
} else {
|
|
rem = 0;
|
|
}
|
|
}
|
|
if rem == 0 {
|
|
digits.pop();
|
|
} else {
|
|
digits[len2] = rem;
|
|
}
|
|
digits
|
|
},
|
|
Ordering::Greater => {
|
|
let mut digits = vec![0; len1 + 1];
|
|
let mut rem = 0;
|
|
for (idx, (d1, d2)) in self.digits.iter().zip(other.digits.iter()).enumerate(){
|
|
let mut sum = d1 + d2 + rem;
|
|
if u32::MAX - d1 < d2 + rem {
|
|
rem = 1;
|
|
} else {
|
|
rem = 0;
|
|
}
|
|
digits[idx] = sum;
|
|
}
|
|
for idx in len2..len1{
|
|
let sum = self.digits[idx] + rem;
|
|
digits[idx] = sum;
|
|
if u32::MAX - self.digits[idx] < rem{
|
|
rem = 1;
|
|
} else {
|
|
rem = 0;
|
|
}
|
|
}
|
|
if rem == 0 {
|
|
digits.pop();
|
|
} else {
|
|
digits[len1] = rem;
|
|
}
|
|
digits
|
|
}
|
|
};
|
|
|
|
BigInt{digits}
|
|
}
|
|
}
|
|
|
|
impl Solution {
|
|
pub fn add_binary(a: String, b: String) -> String {
|
|
let aint : BigInt = a.into();
|
|
let bint : BigInt = b.into();
|
|
return String::from(aint + bint);
|
|
}
|
|
} |