Sum of Two Integers Without + Operator

📋

Problem

Imagine a low-level embedded system where addition hardware is unavailable or costly, and you need to add two integers using only bitwise operations.

Given two integers a and b, return the sum of the two integers without using the '+' or '-' operators.

-2^31 <= a, b <= 2^31 - 1

Edge cases: a = 0, b = 0 → 0a = 0, b = 5 → 5a = -1, b = 1 → 0

</>

IDE

def getSum(a: int, b: int) -> int:public int getSum(int a, int b)int getSum(int a, int b)function getSum(a, b)

def getSum(a: int, b: int) -> int:
    # Write your solution here
    pass

class Solution {
    public int getSum(int a, int b) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int getSum(int a, int b) {
    // Write your solution here
    return 0;
}

function getSum(a, b) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Incorrect positive number for negative inputsMissing 32-bit masking and sign conversion causing incorrect handling of negative numbers.✅ Apply mask 0xFFFFFFFF after each operation and convert result to signed int by checking sign bit.

Wrong: Infinite loop or timeoutNot iterating until carry is zero or incorrect loop condition causing infinite loop.✅ Use while loop that continues until carry is zero, updating a and b each iteration.

Wrong: Wrong sum for large inputsEarly loop termination or incorrect carry calculation for large numbers.✅ Ensure carry is correctly calculated as (a & b) << 1 and loop continues until carry is zero.

Wrong: Incorrect overflow behaviorNot simulating 32-bit signed integer overflow properly.✅ Mask intermediate results with 0xFFFFFFFF and convert final result to signed integer.

✓

Test Cases

Focus on handling zero and boundary inputs correctly with masking.

Pay attention to sign bits and carry propagation for negative and large values.

Optimize your solution to iterative bitwise operations to avoid timeouts.

t1_01basic

Input{"a":1,"b":2}

Expected3

⏱ Performance - must finish in 2000ms

1 + 2 = 3, computed using bitwise operations without '+'

💡 Think about how addition can be done using bitwise XOR and AND operations.

💡 Use XOR to add bits without carry and AND to find carry bits, then iterate until no carry remains.

💡 Implement a loop where sum = a XOR b and carry = (a AND b) shifted left by 1, then update a and b accordingly.

Why it failed: Incorrect sum output; likely missed iterating until carry is zero or incorrect carry calculation. Fix by looping until carry is zero and updating a and b properly.

✓ Correctly computes sum using iterative bitwise operations.

t1_02basic

Input{"a":-2,"b":3}

Expected1

⏱ Performance - must finish in 2000ms

-2 + 3 = 1, testing negative and positive integer addition with bitwise operations.

💡 Remember to handle negative numbers using 32-bit two's complement representation.

💡 Mask intermediate results to simulate 32-bit integer overflow behavior.

💡 Use a mask like 0xFFFFFFFF and handle sign bit to get correct negative results.

Why it failed: Fails on negative inputs due to missing 32-bit masking or sign handling. Fix by applying mask and converting result to signed integer.

✓ Handles negative and positive integers correctly with bitwise operations.

t2_01edge

Input{"a":0,"b":0}

Expected0

⏱ Performance - must finish in 2000ms

Sum of zero and zero is zero; tests empty or zero input handling.

💡 Check if your code handles zero inputs without unnecessary loops.

💡 Ensure that when both inputs are zero, the function returns zero immediately.

💡 Add a condition to return early if carry and sum are zero to avoid infinite loops.

Why it failed: Infinite loop or incorrect output when both inputs are zero due to missing base case. Fix by returning zero immediately if both inputs are zero.

✓ Correctly returns zero for zero inputs without extra computation.

t2_02edge

Input{"a":0,"b":5}

Expected5

⏱ Performance - must finish in 2000ms

Sum of zero and positive integer; tests single operand zero handling.

💡 Verify that adding zero to a number returns the number itself.

💡 Check that carry calculation does not interfere when one operand is zero.

💡 Ensure the loop terminates correctly when carry is zero after first iteration.

Why it failed: Incorrect output when one operand is zero due to improper carry or loop condition. Fix by correctly handling carry and sum updates.

✓ Correctly returns the non-zero operand when the other is zero.

t2_03edge

Input{"a":2147483647,"b":1}

Expected-2147483648

⏱ Performance - must finish in 2000ms

Sum of max 32-bit signed int and 1 causes overflow to min 32-bit signed int.

💡 Remember to simulate 32-bit integer overflow using masking.

💡 Use a mask like 0xFFFFFFFF to keep results within 32 bits.

💡 Convert final result to signed integer by checking if sign bit is set.

Why it failed: Fails to simulate 32-bit overflow, returning incorrect large positive number. Fix by applying 32-bit mask and converting to signed integer.

✓ Correctly simulates 32-bit overflow behavior.

t3_01corner

Input{"a":-1,"b":1}

Expected0

⏱ Performance - must finish in 2000ms

Sum of -1 and 1 is zero; tests correct handling of negative and positive canceling out.

💡 Check how two's complement negative numbers are represented in 32 bits.

💡 Ensure carry and sum calculations handle sign bits correctly.

💡 Use masking and sign conversion to get correct zero result.

Why it failed: Incorrect output due to sign bit mismanagement or missing masking. Fix by applying 32-bit mask and converting to signed integer after computation.

✓ Correctly computes sum of negative and positive numbers cancelling out.

t3_02corner

Input{"a":123456789,"b":987654321}

Expected1111111110

⏱ Performance - must finish in 2000ms

Large positive numbers sum; tests correctness beyond small integers.

💡 Test your bitwise addition logic with large numbers to ensure no truncation.

💡 Check that carry propagation works correctly across all bits.

💡 Verify loop continues until carry is zero for large inputs.

Why it failed: Fails on large inputs due to incomplete carry propagation or early loop termination. Fix by looping until carry is zero.

✓ Correctly sums large positive integers using bitwise operations.

t3_03corner

Input{"a":-2147483648,"b":-1}

Expected2147483647

⏱ Performance - must finish in 2000ms

Sum of min 32-bit signed int and -1 causes overflow to max 32-bit signed int.

💡 Handle negative overflow by simulating 32-bit signed integer wrap-around.

💡 Apply 32-bit mask after each iteration to keep within bounds.

💡 Convert final result to signed integer considering sign bit.

Why it failed: Incorrect output due to missing overflow wrap-around simulation. Fix by masking and sign conversion after computation.

✓ Correctly simulates 32-bit signed integer overflow for negative overflow.

t4_01performance

Input{"a":2147483647,"b":2147483647}

Expectednull

⏱ Performance - must finish in 2000ms

Sum of two max 32-bit signed integers; tests performance and efficiency of bitwise iterative approach.

💡 Bitwise addition runs in O(log(max(a,b))) time, which is efficient for 32-bit integers.

💡 Avoid recursive solutions that may cause stack overflow or slower performance.

💡 Use iterative approach with masking to ensure performance within time limits.

Why it failed: TLE due to exponential or recursive approach without memoization. Fix by using iterative bitwise sum with carry loop.

✓ Efficiently computes sum within time limits using iterative bitwise operations.

Practice

1. You need to generate a sequence of numbers where each consecutive pair differs in exactly one bit, covering all 2^n numbers. Which approach guarantees an optimal and correct solution for this problem?

easy

A. Use a greedy algorithm that flips the least significant bit not used before.

B. Generate the sequence using the reflected Gray code construction method recursively.

C. Apply dynamic programming to build sequences by combining smaller subproblems.

D. Use brute force backtracking to try all permutations and check bit differences.

Solution

1. Step 1: Understand the problem constraints

   The problem requires a sequence of 2^n numbers where each consecutive number differs by exactly one bit.

2. Step 2: Identify the approach that guarantees correctness and efficiency

   The reflected Gray code construction recursively builds the sequence by reflecting and prefixing bits, ensuring the one-bit difference property and covering all numbers exactly once.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Reflected Gray code is the classic, proven method for this problem [OK]

Hint: Reflected Gray code ensures one-bit difference and full coverage [OK]

Common Mistakes:

• Greedy flipping bits can miss valid sequences or repeat numbers
• Brute force is correct but impractical for large n
• DP is not suitable as this is not a subproblem overlapping problem

2. Given the following Python function for UTF-8 validation, what is the value of the variable remaining after processing the second byte in the input [197, 130, 1]?

def validUtf8(data):
    remaining = 0
    for byte in data:
        if remaining == 0:
            if (byte >> 5) == 0b110:
                remaining = 1
            elif (byte >> 4) == 0b1110:
                remaining = 2
            elif (byte >> 3) == 0b11110:
                remaining = 3
            elif (byte >> 7) == 0:
                remaining = 0
            else:
                return False
        else:
            if (byte >> 6) != 0b10:
                return False
            remaining -= 1
    return remaining == 0

easy

A. 2

B. 0

C. 1

D. False (function returns early)

Solution

1. Step 1: Trace first byte (197)

   197 in binary is 11000101. (197 >> 5) == 0b110, so remaining is set to 1.

2. Step 2: Trace second byte (130)

   Since remaining is 1, check if (130 >> 6) == 0b10. 130 in binary is 10000010, so condition holds and remaining is decremented to 0.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Remaining after second byte is 1 -> decremented to 0 after processing second byte [OK]

Hint: Check bit shifts and decrement continuation counter correctly [OK]

Common Mistakes:

• Off-by-one decrement of remaining
• Misinterpreting bit shifts for continuation bytes

3. The following code attempts to find two missing numbers using XOR partitioning but sometimes returns incorrect results. Identify the bug.

medium

A. Final return statement returning [x, y]

B. Line calculating xor_all with XOR of all numbers

C. Loop partitioning numbers based on set_bit

D. Line calculating set_bit using bitwise OR instead of AND

Solution

1. Step 1: Understand set_bit calculation

   Correct approach finds rightmost set bit using xor_all & (-xor_all). Using OR instead breaks partitioning.

2. Step 2: Consequence of bug

   Incorrect set_bit causes wrong grouping of numbers, leading to incorrect missing numbers returned.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Replacing OR with AND fixes partitioning and output [OK]

Hint: Rightmost set bit must be found with AND, not OR [OK]

Common Mistakes:

• Using OR instead of AND for set bit
• Misplacing XOR operations
• Returning wrong variables

4. Suppose you want to generate all permutations of n elements but now elements can be reused any number of times (i.e., permutations with repetition). Which modification to the bitmask DP approach is correct?

hard

A. Use iterative DP over sequence length without bitmask since visited state is irrelevant

B. Keep bitmask DP but allow setting bits multiple times to reuse elements

C. Remove bitmask tracking and use simple recursion with repeated choices allowed

D. Use bitmask DP but reset dp states after each iteration to allow reuse

Solution

1. Step 1: Understand reuse means no visited tracking needed

   Since elements can be reused, the visited bitmask is no longer meaningful.

2. Step 2: Use DP over sequence length only

   Iterative DP over length with choices from all elements at each step correctly generates permutations with repetition.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask DP is unnecessary when elements can be reused [OK]

Hint: Reuse means no visited bitmask needed; track length only [OK]

Common Mistakes:

• Trying to reuse bitmask DP without modification
• Allowing bits to be set multiple times breaks bitmask logic

5. Suppose the UTF-8 validation problem is extended to allow the input data array to be a stream where bytes arrive incrementally, and you must validate the stream in real-time without storing the entire input. Which modification to the optimal algorithm is necessary to correctly validate the stream?

hard

A. Maintain a continuation byte counter and validate each byte as it arrives, returning False immediately on invalid bytes.

B. Use recursion to validate each character once the full character bytes are available.

C. Buffer all bytes until a full character is received before validating to handle partial characters.

D. Reset the continuation byte counter to zero after every 4 bytes to avoid overflow.

Solution

1. Step 1: Understand streaming constraints

   In a stream, bytes arrive incrementally and must be validated on the fly without full buffering.

2. Step 2: Adapt the continuation byte counter approach

   Maintain the continuation byte counter state across bytes and validate each byte immediately, returning False if invalid.

3. Step 3: Avoid buffering or recursion

   Buffering or recursion delays validation and is not suitable for real-time streaming.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Continuation counter with immediate validation fits streaming constraints [OK]

Hint: Maintain state and validate bytes immediately in streaming [OK]

Common Mistakes:

• Buffering entire characters breaks streaming
• Resetting counter incorrectly loses state