Bit Manipulation Flashcards
Summing Binary Numbers
When summing two binary numbers, you carry a 2 (instead of carrying a 10, like in base 10). Therefore 1+ 1 becomes 10. The 0 digit is left behind while the 1 is added to the next digit.
Subtracting Binary Numbers
When subtracting two binary numbers you barrow a 2 (instead of a 10 like in base 10). 0 - 1 becomes 10 - 1 = 1 with the 2 narrowed from the adjacent digit. Subtract the larger from the smaller always. You can always add a negative value afterwards if needed.
Multiplying Two Binary Numbers
When multiplying two binary numbers, we multiply just like in base 10. Start with the lowest digit and multiply it out. Then second digit, but with a zero place holder. This is done for all digits and the results are summed. Since the values of all digits are either 0 or 1, each digit will either zero out or shift the second number.
x ^ 0 (XOR)
x
x ^ 1 (XOR)
~x
x ^ x
0
x & 0
0
x & 1
x
x & x
x
x | 0
x
x | 1
1
x | x
x
Two’s Complement
A positive number is represented as itself while a negative number is represented as the two’s complement of its absolute value (with a 1 in its sign bit, indicating negative). Two’s complement of N-bit number (N does not include the sign bit) is the complement of the number with respect 2N. (The complement of K w.r.t. 2N is 2**N - K). Another way to do this is to invert the bits in the positive representation and then add 1. This is so the zero value is preserved in both the negative and positive representation as all zeros.
Arithmetic Right Shift
Essentially divided by 2. Shift values to the right but fill in the new bits with the value of the sign bit. Indicated by a»_space; operator.
Logical Right Shift
Essentially shifts bits. Shifts the bits and put a 0 in the most significant bit. Indicated with a»_space;> operator.
Get Bit
Shifts 1 over by i bits and ANDs it with a number returning all zeros except at position i. If the number is zero, the number at bit i is zero. Otherwise it is one.
Set Bit
Shifts 1 over by i bits and ORs it with a number. All numbers will change except the bit at position i which will be 1 no matter what
Clear Bit
Shift 1 over i times then negate. AND with a number to flip the bit at position i and leave the rest unchanged.
Clear all bits from the most significant bit through i (inclusive)
Create a mask with a 1 at the ith bit. Subtract 1 from the mask creating a sequence of zeros and i ones. We then AND the mask with the number leaving just the last i bits.
Clear all bits from i through 0 (inclusive)
Sequence of all ones (-1) and shift left by i+1 bits. This gives a sequence of ones (in the most significant bits) followed by i+1 zeros.
Update Bit
Clear the bit at position i by using a mask of ones with 0 at bit i. Then shift the value v, left by i bits. OR shifted v with number to replace the ith bit of number with v and leave all other bits unchanged.
