Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1507
Question Name: Add Two Numbers
Question Description: Compute the sum of two integers without addition, subtraction, multiplication and division.
Input: the input might contain multiple test cases. Each line, as a test case, contains two integers N and M (1 <= N, M <= 1000000).
Output: print the sum of N and M.
1 2 3 4 5 6 | Input: 3 4 7 9 Output: 7 16 |
The solution uses bit operations.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | /*---------------------------------------------------------------- * Author: Sheng Yu - codesays.com * Written: 09/13/2014 * Last updated: 09/13/2014 * * Filename: AddTwoNumbers.java * Compilation: javac AddTwoNumbers.java * Execution: java AddTwoNumbers * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * Add two number without +, -, * and /. * @author Sheng Yu codesays.com */ public class AddTwoNumbers { /** * Add two numbers without +, -, * and /. * @param n the first number. * @param m the second number. * @return the sum of the these two numbers. */ public static int add(int n, int m) { // The pre-computed table for the addition with two bit and // one carry bit. // All the index and value are explained as binary form. // For example computeTab[0bXYZ] = 0bNM means // Z is the bit from the first number, Y is the bit from the // second number, and Z is the carry bit. If add them, // the current bit will be M, and new carry bit would be N. // // Java 1.6, which is used in OJ system, does not support 0bXXX. //final int[] computeTab = new int[] {0b00, 0b01, 0b01, 0b10, // 0b01, 0b10, 0b10, 0b11}; // final int[] computeTab = new int[] {0, 1, 1, 2, 1, 2, 2, 3}; int result = 0; int carry = 0; int input = 0; int output = 0; for (int bit = 0; bit < 32; ++bit) { // Get the input for the bit(th) bit in both numbers and carry. input = (carry << 2) | (((n >> bit) & 1) << 1) | ((m >> bit) & 1); // Get the pre-computed sum. output = computeTab[input]; carry = (output >> 1) & 1; result |= ((output & 1) << bit); } return result; } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int n = 0; int m = 0; while (st.nextToken() != StreamTokenizer.TT_EOF) { n = (int) st.nval; st.nextToken(); m = (int) st.nval; System.out.println(add(n, m)); } } } |