Bitwise Operations

Note: Bitwise operations shown here are only considered on natural numbers. In fact, bitwise operations can also be performed on negative numbers, but we won’t discuss their nature here.

AND / OR / XOR Operations

Bitwise AND, OR, and XOR are binary operations (two operands). These operations are performed independently on each bit and then combined to form the final result.

Bitwise AND, symbol: a & b

For each bit x and y, AND is performed as follows:

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

Explanation: returns 1 only when both bits are 1; returns 0 otherwise.

368 = 101110000
147 =  10010011
→ align bits to same width:
368 = 101110000
147 = 010010011
368 & 147 = 000010000 = 16

Bitwise OR, symbol: a | b

For each bit x and y, OR is performed as follows:

0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

Explanation: returns 1 if at least one of the bits is 1; returns 0 only if both are 0.

368 = 101110000
147 = 010010011
368 | 147 = 111110011 = 499

Bitwise XOR, symbol: a ^ b

For each bit x and y, XOR is performed as follows:

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

Explanation: returns 1 if bits are different; returns 0 if they are the same.

368 = 101110000
147 = 010010011
368 ^ 147 = 111100011 = 483

Special Properties of XOR:

• a ^ 0 = a for all a
• a ^ a = 0 for all a
• XOR is its own inverse

XOR is the “inverse operation” of itself

a + b = S → a = S — b or b = S — a
a * b = P → a = P / b or b = P / a
a ^ b = X → a = X ^ b or b = X ^ a

When summing over a set of numbers, remember:
+ Any number XOR with itself = 0
+ A value that appears twice is considered as not appearing
+ A value that appears an odd number of times is considered as appearing once

Example:

1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 3 ^ 2 ^ 2 ^ 3 ^ 3 ^ 4 ^ 4 ^ 4 ^ 4 ^ 5

→ 1 appears twice → gone
→ 2 appears 4 times → gone
→ 3 appears 4 times → gone
→ 4 appears 4 times → gone
→ 5 appears once → remains

Result: 5

Bit Shift Operations

Left Shift, symbol: a << b

Meaning:

• In binary: add b zeros to the right of a
• Value: multiply a by 2^b

368 = 101110000
368 << 4 = 1011100000000
→ 368 * 2^4 = 368 * 16 = 5888

147 = 10010011
147 << 2 = 1001001100
→ 147 * 2^2 = 147 * 4 = 588

Right Shift, symbol: a >> b

Meaning:

• In binary: remove b bits from the right side of a
• Value: divide a by 2^b (rounded down)

368 = 101110000
368 >> 4 = 000010111 = 23
→ 368 / 2^4 = 368 / 16 = 23

147 = 10010011
147 >> 2 = 00100100 = 36
→ 147 / 4 = 36.75 → truncated to 36

Bitwise NOT (~)

Symbol: ~

This is a unary operator (only one operand). For each bit i:

• If bit i of a is 1, then bit i of is 0
• If bit i of a is 0, then bit i of is 1

Note: In C/C++, bitwise NOT gives result: -a — 1

~368 = -369
~147 = -148

Common Mistakes When Using Bitwise Operations

- You must distinguish between bitwise operations and logical expression operations.

Bitwise AND & is a bitwise operator,
Logical AND && is a logical expression operator
→ & returns any integer result
→ && only returns 0 or 1 (TRUE or FALSE)

Bitwise OR | is a bitwise operator,
Logical OR || is a logical expression operator
→ | returns any integer result
→ || only returns 0 or 1 (TRUE or FALSE)

Bitwise XOR ^ is a bitwise operator,
Logical NOT ! is a logical expression operator
→ ^ returns any integer result
→ ! only returns 0 or 1 (TRUE or FALSE)

- When using bitwise operations (& | ~ ^ << >>), always use parentheses to group expressions. Otherwise, operator precedence may cause unexpected behavior.