Bit Manipulation

Question 1

Summing Binary Numbers

Answer 1

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.

Question 2

Subtracting Binary Numbers

Answer 2

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.

Question 3

Multiplying Two Binary Numbers

Answer 3

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.

Question 4

x ^ 0 (XOR)

Answer 4

x

Question 5

x ^ 1 (XOR)

Answer 5

~x

Question 6

x ^ x

Answer 6

0

Question 7

x & 0

Answer 7

0

Question 8

x & 1

Answer 8

x

Question 9

x & x

Answer 9

x

Question 10

x | 0

Answer 10

x

Question 11

x | 1

Answer 11

1

Question 12

x | x

Answer 12

x

Question 13

Two’s Complement

Answer 13

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.

Question 14

Arithmetic Right Shift

Answer 14

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&raquo_space; operator.

Question 15

Logical Right Shift

Answer 15

Essentially shifts bits. Shifts the bits and put a 0 in the most significant bit. Indicated with a&raquo_space;> operator.

Question 16

Get Bit

Answer 16

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.

Question 17

Set Bit

Answer 17

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

Question 18

Clear Bit

Answer 18

Shift 1 over i times then negate. AND with a number to flip the bit at position i and leave the rest unchanged.

Question 19

Clear all bits from the most significant bit through i (inclusive)

Answer 19

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.

Question 20

Clear all bits from i through 0 (inclusive)

Answer 20

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.

Question 21

Update Bit

Answer 21

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.