How to add two numbers without using ++ or + or another arithmetic operator

by

This is something I have written a while ago for fun. It uses a two’s complement representation and implements addition using repeated shifts with a carry bit, implementing other operators mostly in terms of addition.

#include <stdlib.h> /* atoi() */
#include <stdio.h>  /* (f)printf */
#include <assert.h> /* assert() */

int add(int x, int y) {
    int carry = 0;
    int result = 0;
    int i;

    for(i = 0; i < 32; ++i) {
        int a = (x >> i) & 1;
        int b = (y >> i) & 1;
        result |= ((a ^ b) ^ carry) << i;
        carry = (a & b) | (b & carry) | (carry & a);
    }

    return result;
}

int negate(int x) {
    return add(~x, 1);
}

int subtract(int x, int y) {
    return add(x, negate(y));
}

int is_even(int n) {
    return !(n & 1);
}

int divide_by_two(int n) {
    return n >> 1;
}

int multiply_by_two(int n) {
    return n << 1;
}

int multiply(int x, int y) {
    int result = 0;

    if(x < 0 && y < 0) {
        return multiply(negate(x), negate(y));
    }

    if(x >= 0 && y < 0) {
        return multiply(y, x);
    }

    while(y > 0) {
        if(is_even(y)) {
            x = multiply_by_two(x);
            y = divide_by_two(y);
        } else {
            result = add(result, x);
            y = add(y, -1);
        }
    }

    return result;
}

int main(int argc, char **argv) {
    int from = -100, to = 100;
    int i, j;

    for(i = from; i <= to; ++i) {
        assert(0 - i == negate(i));
        assert(((i % 2) == 0) == is_even(i));
        assert(i * 2 == multiply_by_two(i));
        if(is_even(i)) {
            assert(i / 2 == divide_by_two(i));
        }
    }

    for(i = from; i <= to; ++i) {
        for(j = from; j <= to; ++j) {
            assert(i + j == add(i, j));
            assert(i - j == subtract(i, j));
            assert(i * j == multiply(i, j));
        }
    }

    return 0;
}

More Related Contents:

  1. What is the efficient way to count set bits at a position or lower?
  2. How can I test whether a number is a power of 2?
  3. find the number of times a character occurs between two indexes
  4. Program to find sum of prime numbers between 1 and 10^7
  5. Invalid solution for code challenge with operator restrictions
  6. Which is the fastest algorithm to find prime numbers?
  7. Position of least significant bit that is set
  8. Rounding up to the nearest multiple of a number
  9. Magic number in boost::hash_combine
  10. Creating all possible k combinations of n items in C++
  11. Finding all the subsets of a set
  12. How do I calculate the week number given a date?
  13. C/C++ check if one bit is set in, i.e. int variable
  14. Efficient implementation of log2(__m256d) in AVX2
  15. Where can I get a “useful” C++ binary search algorithm?
  16. C++: Converting Hexadecimal to Decimal
  17. Printing prime numbers from 1 through 100
  18. Circular lock-free buffer
  19. Generating m distinct random numbers in the range [0..n-1]
  20. TMP: how to generalize a Cartesian Product of Vectors?
  21. Efficient bitwise operations for counting bits or find the right|left most ones
  22. Efficiently getting all divisors of a given number
  23. What’s the quickest way to compute log2 of an integer in C#?
  24. Branchless code that maps zero, negative, and positive to 0, 1, 2
  25. Is it possible to map string to int faster than using hashmap?
  26. Is it possible to implement lock free map in C++
  27. stl ordering – strict weak ordering
  28. How to set, clear, and toggle a single bit?
  29. Calculate mean and standard deviation from a vector of samples in C++ using Boost
  30. Checking if all elements of a vector are equal in C++

Leave a Comment