Add Two Numbers (Bitwise)
Perform integer addition using only bitwise operations (XOR, AND, shift) without the + operator, mimicking how CPUs add numbers at the hardware level using logic gates. This algorithm decomposes addition into sum-without-carry (XOR) and carry-generation (AND + shift), iterating until no carry remains. Fundamental for understanding computer architecture, ALU design, and implementing arithmetic when + operator is unavailable or expensive.
Visualization
Interactive visualization for Add Two Numbers (Bitwise)
Interactive visualization with step-by-step execution
Implementation
1function bitwiseAdd(a: number, b: number): number {
2 while (b !== 0) {
3 const carry = a & b;
4 a = a ^ b;
5 b = carry << 1;
6 }
7 return a;
8}Deep Dive
Theoretical Foundation
Binary addition can be decomposed into two independent operations that mirror full-adder circuit behavior: (1) Sum without carry: XOR gives sum bit when no carry considered (0+0=0, 0+1=1, 1+0=1, 1+1=0). (2) Carry generation: AND finds where both bits are 1 (generating carry), then left-shift moves carries to next position. Algorithm: repeatedly compute sum=a⊕b and carry=(a&b)<<1, replace a=sum and b=carry, until carry=0. Correctness: each iteration processes one level of carries. Termination: carry propagates at most log(n) bits (for n-bit numbers). Time: O(log n) iterations where n is larger number. This is how full-adder circuits work in hardware!
Complexity
Time
O(1)
O(log n)
O(log n)
Space
O(1)
Applications
Industry Use
ALU (Arithmetic Logic Unit) implementation
FPGA and hardware design
Cryptographic algorithms
Low-level systems programming
Educational demonstrations of binary arithmetic
Embedded systems without FPU
Interview questions on bit manipulation
Understanding CPU architecture
Use Cases
Related Algorithms
Count Set Bits (Brian Kernighan's Algorithm)
Efficiently count the number of 1 bits (set bits) in the binary representation of an integer. Brian Kernighan's algorithm is one of the most elegant bit manipulation techniques, invented by Brian Kernighan (co-author of 'The C Programming Language'). The algorithm repeatedly clears the rightmost set bit, making it optimal as it only loops for the number of set bits rather than all bits.
Check if Power of Two
Determine if a given integer is a power of 2 using a brilliant single bitwise operation. Powers of 2 in binary have exactly one set bit: 1=0001, 2=0010, 4=0100, 8=1000, 16=10000. This unique property enables an O(1) constant-time check using the elegant formula: n > 0 && (n & (n-1)) == 0. This trick is widely used in systems programming, memory management, and optimization.
XOR Operations Collection
Comprehensive collection of XOR (exclusive OR) bit manipulation techniques with unique mathematical properties: a ⊕ a = 0 (self-inverse), a ⊕ 0 = a (identity), commutative, and associative. XOR is fundamental in finding unique/missing elements, in-place swapping, parity checking, cryptography, error detection, and many optimization problems. These elegant properties make XOR one of the most powerful bitwise operators.
Reverse Bits
Reverse the bit pattern of a 32-bit unsigned integer efficiently using bit manipulation. For example, 43261596 (binary: 00000010100101000001111010011100) becomes 964176192 (binary: 00111001011110000010100101000000) after reversal. This operation is critical in Fast Fourier Transform (FFT) bit-reversal permutation, graphics processing, cryptographic operations, and understanding little-endian/big-endian conversions at the bit level.