Bitwise Arithmetic

Bitwise Arithmetic

Computers store integers as binary patterns containing only 0s and 1s. Arithmetic instructions such as addition and subtraction are implemented by processor circuits that operate on these binary values.

At the programming level, using +, -, *, and / is normally the clearest and most efficient choice. The compiler translates these operators into suitable processor instructions.

However, learning bitwise arithmetic helps us understand:

• How binary addition produces sum and carry bits

• How negative numbers are represented

• How multiplication and division by powers of two relate to shifts

• How arithmetic can be implemented using bitwise operators

• Why certain bitwise identities work

• How hardware arithmetic circuits are designed

Bitwise arithmetic is especially relevant in interview problems that restrict the use of standard arithmetic operators.

What Is Bitwise Arithmetic?

Bitwise arithmetic uses operators such as:

• XOR (^)

• AND (&)

• NOT (~)

• Left shift (<<)

• Right shift (>>)

to reproduce or support arithmetic operations on binary values.

This does not mean that bitwise replacements are automatically faster than normal arithmetic. Modern processors contain dedicated arithmetic instructions, and compilers already perform many safe optimizations.

The primary purpose of bitwise arithmetic in DSA is to understand binary behaviour and solve problems with specific operator restrictions.

Understanding Binary Addition

Binary addition follows the same carry-based idea as decimal addition, but it uses only 0 and 1.

The possible additions of two bits are:

When both bits are 1:

1 + 1 = 10₂

The sum bit is 0, while the carry bit 1 moves to the next position on the left.

The two output columns match familiar bitwise operators:

Sum without carry = A ^ B

Carry = A & B

Because the carry belongs to the next binary position, it must be shifted left:

Shifted Carry = (A & B) << 1

Adding Two Numbers Without the Plus Operator

To add two complete binary numbers:

• XOR produces their current sum without carry.

• AND identifies the positions that generate a carry.

• Left shift moves each carry to the next position.

• The process repeats using the partial sum and shifted carry.

• Addition finishes when no carry remains.

The two important expressions are:

partialSum = A ^ B

carry = (A & B) << 1

After calculating them:

• Replace A with partialSum.

• Replace B with carry.

• Repeat until B becomes 0.

At that point, A contains the final sum.

Algorithm

• Treat A as the current partial sum and B as the carry still waiting to be added.

• Use XOR to combine them without carrying between bit positions.

• Use AND to locate positions where both bits are set and therefore generate a carry.

• Shift the carry left by one position because it belongs to the next binary column.

• Continue with the new partial sum and carry until no carry remains.

• Return the final partial sum as the result.

Dry Run: Add 5 and 3

Why Does the Process Terminate?

Every carry is shifted one position to the left.

For a fixed-width integer, a carry cannot continue moving left indefinitely. It either:

• Finds a position where no new carry is generated, or

• Moves beyond the available bit width

Therefore, for a W-bit integer, the process requires at most O(W) iterations.

For fixed 32-bit or 64-bit integers, W is constant, so this is commonly treated as:

Time Complexity: O(1)

Space Complexity: O(1)

For arbitrary-precision integers, the cost depends on the number of bits being processed.

A hardware adder does not necessarily execute this exact software loop. Processors use specialized circuits that propagate or predict carries more efficiently.

Subtraction Using Bitwise Arithmetic

In fixed-width two’s-complement arithmetic, subtracting B from A can be rewritten as:

A - B = A + (-B)

The two’s-complement representation of -B is:

-B = ~B + 1

Therefore:

A - B = A + (~B + 1)

The resulting addition can be performed using the XOR-and-carry process.

Example: Subtract 5 from 9

Using eight-bit representations:

9 = 00001001

5 = 00000101

Flip every bit of 5:

~5 = 11111010

Add 1:

11111010 + 1 = 11111011

This is the eight-bit two’s-complement representation of -5.

Now add it to 9:

00001001 + 11111011 = 1 00000100

The carry beyond the eight-bit width is discarded.

The remaining value is:

00000100 = 4

Therefore:

9 - 5 = 4

Multiplication Using Shifts

A left shift by K positions corresponds to multiplication by 2ᴷ when:

• The value is non-negative

• The result remains representable

• No important bit is discarded

The relation is:

N << K = N × 2ᴷ

For example:

6 << 1 = 12

6 << 2 = 24

Multiplication by a General Number

A multiplier can be decomposed into powers of two using its binary representation.

Consider:

6 × 5

The binary representation of 5 is:

101₂ = 2² + 2⁰

Therefore:

6 × 5 = (6 × 2²) + (6 × 2⁰)

Using shifts:

= (6 << 2) + 6

= 24 + 6

= 30

General binary multiplication examines each set bit of the multiplier. For every set bit, an appropriately shifted copy of the multiplicand contributes to the result.

This is commonly called the shift-and-add method.

Division Using Shifts

For a non-negative integer:

N >> K

corresponds to floor division by 2ᴷ.

For example:

13 >> 1 = 6

because:

13 ÷ 2 = 6 with the fractional part discarded.

Similarly:

20 >> 2 = 5

because:

20 ÷ 4 = 5

This relation requires caution with negative values. Signed right shift and signed integer division may use different rounding behaviour depending on the language.

Division by an arbitrary number cannot generally be replaced with one right shift. More advanced binary division algorithms use repeated comparisons, shifts, and subtraction.

Essential Bitwise Formulas

Checking Whether a Number Is Even or Odd

The least significant bit determines parity:

• Even numbers end in 0.

• Odd numbers end in 1.

To test the final bit:

N & 1

If the result is 0, the number is even.

If the result is non-zero, the number is odd.

Examples:

10 = 1010

1010 & 0001 = 0000

Therefore, 10 is even.

7 = 0111

0111 & 0001 = 0001

Therefore, 7 is odd.

This expresses parity directly through the binary representation. It should not be used merely under the assumption that it is always faster than modulo; compilers commonly optimize simple parity checks.

Clearing the Lowest Set Bit

The expression:

N & (N - 1)

clears the rightmost set bit of N.

Consider:

N = 12 = 1100

N - 1 = 11 = 1011

Applying AND:

1100 & 1011 = 1000

The lowest set bit has been removed.

This identity is used in Brian Kernighan’s algorithm to count set bits by repeatedly removing one set bit at a time.

Swapping with XOR

Two values can be swapped using XOR:

A = A ^ B

B = A ^ B

A = A ^ B

This works because XOR is reversible. However, it is generally not recommended in normal code because:

• It is less readable than a regular swap.

• Modern compilers already optimize ordinary swaps.

• It can fail when both expressions refer to the same storage location.

• It does not provide a dependable performance advantage.

It is better treated as an XOR property demonstration than as an optimization.

Fixed-Width and Signed-Number Behaviour

Bitwise arithmetic is easiest to reason about when the integer width is known.

For a W-bit unsigned integer, results are interpreted modulo:

2ᵂ

Bits that move beyond the available width are discarded.

Signed integers require additional caution:

• The highest bit commonly represents the sign under two’s complement.

• Left shifting into or beyond the sign bit can produce invalid or language-dependent behaviour.

• Right shifting a negative value may copy the sign bit.

• Signed arithmetic overflow may not behave consistently across languages.

• Arbitrary-precision languages do not have the same fixed-width boundaries.

When the exact bit pattern matters, fixed-width unsigned values usually provide the clearest model.

Language-Specific Considerations

C and C++

• Shifting by a negative amount or by an amount greater than or equal to the type width is invalid.

• Signed overflow must not be relied upon.

• Unsigned types provide predictable modulo arithmetic.

• A sufficiently wide mask should be used when accessing high bit positions.

Java

• Signed integers use fixed widths and two’s-complement representation.

• >> performs a sign-preserving right shift.

• >>> performs a zero-filling right shift.

• Shift counts are processed according to the width of the operand type.

Python

• Integers have arbitrary precision rather than a fixed 32-bit or 64-bit width.

• Negative integers behave as though they have infinitely many leading 1 bits.

• A fixed-width mask is usually required when emulating bounded integer arithmetic.

• An addition loop written for unsigned fixed-width values may require special handling for negative inputs.

Operator Precedence

Expressions combining bitwise operators, comparisons, and arithmetic should use explicit parentheses.

In C++ and Java, equality operators have higher precedence than bitwise AND. Therefore:

N & 1 == 0

may not be interpreted as the intended parity check.

Write:

(N & 1) == 0

Similarly, make the grouping clear in expressions such as:

(A ^ B) == 0

or:

((A & B) << 1)

Precedence differs across languages, so explicit grouping improves correctness and readability.

When Is Bitwise Arithmetic Useful?

Bitwise arithmetic is useful when:

• A problem forbids +, -, *, or /.

• Hardware arithmetic needs to be understood.

• Values represent masks, flags, or binary states.

• Multiplication or division specifically involves powers of two.

• Two’s-complement behaviour is part of the problem.

• An embedded or systems-level task requires precise bit control.

• A bit-counting or power-of-two identity simplifies the solution.

For ordinary application code, standard arithmetic operators should remain the default because they are clearer and already map to efficient instructions.

Common Mistakes

• Assuming a bitwise replacement is automatically faster than normal arithmetic.

• Forgetting that XOR gives the sum only when carry is ignored.

• Forgetting to shift the carry one position to the left.

• Stopping the addition process before the carry becomes zero.

• Applying a fixed-width negative-number method directly to Python without masking.

• Using signed values when predictable unsigned behaviour is required.

• Assuming left shift cannot overflow or discard high bits.

• Assuming right shift matches division for every negative number.

• Shifting by a negative count or by at least the width of the type.

• Mixing bitwise operators with comparisons without parentheses.

• Using XOR swap as a production optimization.

• Treating N << K as general multiplication by any value.

• Forgetting to exclude zero while checking for a power of two.

FAQs

Q1. Does addition using XOR and AND work for negative numbers?

It works naturally within a defined fixed-width two’s-complement model. In languages with arbitrary-precision integers, such as Python, negative values require an explicit width and mask because their bit representation behaves as though it has infinitely many leading sign bits.

Q2. Can bitwise addition overflow?

Yes. It produces the same fixed-width mathematical result as ordinary binary addition. If the exact result does not fit in the selected width, high bits may be discarded for unsigned arithmetic, while signed overflow behaviour depends on the language.

Q3. Why is right shift not always equivalent to integer division for negative numbers?

Right shift commonly preserves the sign and behaves like rounding toward negative infinity, while integer division in some languages truncates toward zero. For example, shifting -3 right may produce -2, whereas division of -3 by 2 may produce -1.

Q4. Is rewriting arithmetic with bitwise operators faster?

Not necessarily. Processors already provide efficient arithmetic instructions, and compilers optimize common operations. Bitwise arithmetic should be used when it represents the problem naturally or when standard arithmetic operators are restricted, not as an automatic performance optimization.

Q5. How can arbitrary multiplication be performed using bitwise operations?

Examine the binary bits of the multiplier. For every set bit at position i, add the multiplicand shifted left by i. This shift-and-add process constructs the product from powers of two.