# 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 2**N. (The complement of K w.r.t. 2**N 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.