Bit Manipulation:
Important Concepts
- Basic Bitwise Operations
- Bit Tricks
- Two’s Complement
- Shifts: Arithmetic vs Logical
- Common Bit Tasks
Bit Operators:
Three Types of Operators
- Basic Arithmetic
- Boolean Operators
- Shifts
Bit Operators:
Basic Arithmetic Operators
- Addition: +
- Subtraction: -
- Multiplication: *
- Division: \
Bit Operators:
Boolean Operators
- Bitwise AND: &
- Bitwise OR: |
- Bitwise Exclusive OR(XOR): ^
- Bitwise NOT: ~ * Bitwise
Bit Operators:
Shifts
Arithmetic Shifts:
* Left: «
* Right:»_space;
Logical Shifts:
* Left: «<
* Right:»_space;>
Bitwise Identities:
X | 0s = ?
X | 0s = X
For each bit in X
If 1, operation is 1 | 0 = 1
If 0, operation is 0 | 0 = 0
So, no bits in the result are different from X
Bit Identities:
X ^ 1s = ?
X XOR all ones
X ^ 1s = ~X
For a bit in X:
If 1, 1 ^ 1 = 0
If 0, 0 ^ 1 = 1
All bits are flipped to the opposite
Bit Identities:
X ^ 0s = ?
X XOR all zeros
X ^ 0s = X
For a bit in X:
If 1, 1 ^ 0 = 1
If 0, 0 ^ 0 = 0
All bits in the result are the same as X
Bit Identities:
X ^ X = ?
X XOR X
X ^ X = 0
For each bit in X:
If 1, 1 ^ 1 = 0
If 0, 0 ^ 0 = 0
All bits are set to 0
Bit Identities:
X & 0 = ?
X AND 0
X & 0 = 0
For a bit in X:
If 1, 1 & 0 = 0
If 0, 0 & 0 = 0
Bit Identities:
X & 1s
X AND all ones
X & 1s = X
For a bit in X:
If 1, 1 & 1 = 1
If 0, 1 & 0 = 0
No bits are changed.
Bit Identities:
X & X
X AND X
X & X = X
For a bit in X:
If 1, 1 & 1 = 1
If 0, 0 & 0 = 0
No bits are changed
Bit Identities:
X | 1s
X OR all ones
X | 1s = 1s
For a bit in X:
If 1, 1 | 1 = 1
If 0, 0 | 1 = 1
All bits become ones
Bit Identities:
X | X = ?
X OR X
X | X = X
For a bit in X:
If 1, 1 | 1 = 1
If 0, 0 | 0 = 0
No bits are changed
Bit Tricks:
Add a number to itself:
X + X
- Adding a number to itself is equivalent to multiplying it by 2
- Multiplying by 2 is equivalent to an Arithmetic Left Shift of 1
2X = X «_space;1
So,
X + X = 2X = X «_space;1
Bit Tricks:
Multiplying by a power of 2:
X*(2^n)
Multiplying by 2 is equivalent to an Arithmetic Left Shift of 1.
2X = X «_space;1
So, multiplying X by 2 n times is the same as shifting X n times
X*(2^n) = X «_space;n
Bit Identities:
X ^ ~X = ?
X XOR (NOT X)
X ^ ~X = 1s
For a bit in X:
If 1, 1 ^ 0 = 1
If 0, 0 ^ 1 = 1
All bits are set to 1
What is the typical representation of signed integers called?
Two’s Complement
What is Two’s Complement?
- How signed integers are usually stored
- The most significant bit indicates if a number is positive or negative
- The remaining bits store the value of the number
- Positive numbers store the value normally
- Negative numbers are stored as:
2^(N-1) - K
Where N is the number of bits used( eg, 8, 16, 32, 64)
and K is the absolute value of the integer
Two’s Complement:
How are positive integers stored?
- The first bit is 0, indicating a positive number
- The remaining bits are the binary representation of the number
Example: In a 4-bit system
1 -> 0 001
2 -> 0 010
Two’s Complement:
How are Negative Integers stored?
- The most significant bit is a 1 to indicate a negative value
- The absolute value of the number(K) is subtracted from 2^N,
where N is the number of bits, not including the sign bit
Example: In a 4-bit system
2^N = 2^3
The binary representation of 2^3 = 1000
-1 is represented by 1 [1000 - 001] = 1 [111]
so, -1 = 1111 in Two’s Complement
-2 = 1 [1000 - 010] = 1 [110]
Two’s Complement:
Maximum Absolute Value of integers stored in an N-bit system
2^(N-1) - 1
An N-bit system has N-1 bits to store the absolute value,
as one bit is always used for the sign bit
Two’s Complement:
Converting a positive integer to a negative
- Start with the positive representation
3 -> 011 - Perform NOT operation to “flip” the number
~3 -> 100 - Add 1
101 - Prepend the sign bit
-3 = 1101
Two’s Complement:
Relationship between positive and negative integers
Every positive integer has a negative counterpart,
where the absolute values ALWAYS sum to 2^(N-1)
Example: in a 4-bit system:
1: 0001
-1: 1111
001 + 111 = 1000 = 2^3
2: 0010
-2: 1110
010 + 110 = 1000 = 2^3
This is why it’s called “Two’s Complement”
