Ch 5: Bit Manipulation Flashcards
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”
What is the Two’s Complement binary value of:
7
0 111
What is the Two’s Complement binary value of:
6
0 110
What is the Two’s Complement binary value of:
5
0 101
What is the Two’s Complement binary value of:
4
0 100
What is the Two’s Complement binary value of:
3
0 011
What is the Two’s Complement binary value of:
2
0 010
What is the Two’s Complement binary value of:
1
0 001
What is the Two’s Complement binary value of:
0
0 000
What is the Two’s Complement binary value of:
-1
1 111
What is the Two’s Complement binary value of:
-2
1 110
What is the Two’s Complement binary value of:
-3
1 101
What is the Two’s Complement binary value of:
-4
1 100
What is the Two’s Complement binary value of:
-5
1 011
What is the Two’s Complement binary value of:
-6
1 010
What is the Two’s Complement binary value of:
-7
1 001
Bitwise Operators:
Difference between
Arithmetic Right Shift (»)
and
Logical Right Shift (»>)
Arithmetic Right shift maintains the sign bit and fills in the new bits with whatever the original sign bit is.
Logical Shift does NOT maintain the sign bit,
always fills in the new bits with 0
Bitwise Operators:
Arithmetic Right Shift
x»_space; n
- Shifts all bits to the right, n times
- Fills in new bits with the sign bit:
0 if positive number
1 if negative number - Equivalent to dividing by 2, n times.
Examples:
4»_space; 2:
0 100»_space; 2 = 0 001 = 1
-4»_space; 2:
1 100»_space; 2 = 1 111 = -1
Bitwise Operators:
Logical Right Shift
X»_space;> n
- Shifts all bits to the right, n times
- Fills in new bits with 0
- Does NOT preserve sign bit
- On positive numbers, equivalent to Arithmetic Right Shift
Example:
5»_space;> 1:
0 101»_space;> 1 = 0 010 = 2
-2»_space; 1:
1 110»_space;> 1 = 0 111 = 7
Most common tasks of bit manipulation
- Get Bit
- Set Bit
- Clear Bit
- Clear all bits from i to the left
- Clear all bits from i to the right
- Clear bits from i to j
- Update a bit
Common Bit Tasks:
Get Bit
Goal:
Check if the ith bit of a number is 1 or 0
How:
* Create a mask by shifting 1 (0001) left to the ith position:
1 «_space;i
- AND the mask with the number
- If result is not 0, the ith bit is a 1, else it is 0
- Because only the ith bit of the mask is 1, only the ith bit of the number affects the result.
example:
Check bit 2 of 0101:
mask = 1 «_space;2 = 0001 «_space;2 = 0100
0101 & 0100 = 0100
Common Bit Tasks:
Set Bit
Goal:
Set the ith bit of a number to 1
How:
* Create a mask by shifting 1(0001) to the left to the ith position
1 «_space;i
* OR with the number
* The result is exactly the same as the number, except for the ith bit
* If bit i was already 1, it is the same
Example:
Set bit 2 of 1010:
mask = 1 «_space;2 = 0100
1010 | mask = 1010 | 0100 = 1110
Common Bit Tasks:
Clear Bit
Goal:
Clear the ith bit (set to 0)
How:
* Create a sort of reverse mask:
Shift 1 by i, then negate it
mask = 0001 «_space;2 = 0100
nMask = ~mask = 1011
* AND this mask with the number. The ith bit will be 0, the other bits will remain the same.
Example:
Clear bit 2 of 1101:
result = 1101 & ~(1 «_space;2) = 1001
Common Bit Tasks:
Clear Bits to the Left
Goal:
Clear all bits from the Most Significant Bit to i
How:
* Create a bitmask that is all 1s until i, and 0s from i to MSB
- Shift 1 by i
- Subtract 1
* AND bitmask with number
* Result leaves only bits 0 to i
Example:
Clear bits to left of bit 3 on 1010 1101
Create bitmask:
1 «_space;3 = 0000 1000
Subtract 1
0000 0111
AND with Number:
1010 1101
&0000 0111
——————
= 00000111
Common Bit Tasks:
Clear all bits to the right
Goal:
Clear all bits from 0 to i (right of i, inclusive)
How:
* Create a bitmask that is all 0s from 0 to i, then 1s from i+1 to MSB
* Shift -1 to the left by i+1:
* -1 is always all 1s in two’s complement representation
* AND with the target
Example:
Clear bits to right of bit 3 on 1010 1101
Create bitmask:
-1 «_space;3+1 = 1 111 1111 «_space;4 = 1 111 0000
AND with Number:
1010 1101
&1111 0000
——————
= 1010 0000
