Bitwise Operations (Solutions)

Back to Bitwise Operations

Problem 1

Show that a | b, a ^ b, ~a, and ~b indeed give the expected results from the code output through performing a similar analysis as we did for analyzing a & b from above.

Recall that in this example, we defined int8_t a = 0b00001110 and int8_t b = 0b00100101. We can first calculate the desired expressions using strictly the bitwise operations:

All that is left is to use the two’s complement convention to rewrite each of these binary numbers in base-10:

$$\texttt{a | b}=-2^7(\texttt{0})+2^6(\texttt{0})+2^5(\texttt{1})+2^4(\texttt{0})+2^3(\texttt{1})+2^2(\texttt{1})+2^1(\texttt{1})+2^0(\texttt{1})=47$$

$$\texttt{a ^ b}=-2^7(\texttt{0})+2^6(\texttt{0})+2^5(\texttt{1})+2^4(\texttt{0})+2^3(\texttt{1})+2^2(\texttt{0})+2^1(\texttt{1})+2^0(\texttt{1})=43$$

$$\texttt{~a}=-2^7(\texttt{1})+2^6(\texttt{1})+2^5(\texttt{1})+2^4(\texttt{1})+2^3(\texttt{0})+2^2(\texttt{0})+2^1(\texttt{0})+2^0(\texttt{1})=-15$$

$$\texttt{~a}=-2^7(\texttt{1})+2^6(\texttt{1})+2^5(\texttt{0})+2^4(\texttt{1})+2^3(\texttt{1})+2^2(\texttt{0})+2^1(\texttt{1})+2^0(\texttt{0})=-38$$

If we compare these results with the results from the relevant code sample (shown below again for convenience), we can see that we achieve all of the expected results.

Problem 2

Using a similar analysis and diagram as above, explain the result of the following code:

int8_t a = 0b10001110;
int8_t b = a << 1;

printf("a: %d\n", a); // Prints a: -114
printf("b: %d\n", b); // Prints b: 28

Note that \(2\cdot\texttt{a}=2(\texttt{-114})=\texttt{-228}\), which is less than the minimum bound for int8_t signed integers (-128). Let’s graph this on the number line, producing a similar diagram as in the example preceding this problem.

The overflow distance $x_{ov}$ from the right most upper bound is

\[x_{ov}=-129-(-228)=99\]

Therefore, we can conclude that the value of $\texttt{b}$ is

\[\texttt{b}=127-x_{ov}=127-99=28\]

This agrees with the expected output. Let’s also confirm that this agrees with our understanding of the left arithmetic shift operation:

\[\texttt{b}=\texttt{a<<1}=\texttt{0b00011100}\]

$$\texttt{b}=-2^7(\texttt{0})+2^6(\texttt{0})+2^5(\texttt{0})+2^4(\texttt{0})+2^3(\texttt{1})+2^2(\texttt{1})+2^1(\texttt{1})+2^0(\texttt{0})=28$$

as expected.

Problem 3

The following code in main(void) swaps the values of two int variables n1 and n2 using only bitwise operations. Explain how this function works.

This problem was adapted from GeeksforGeeks. They have a good explanation of the solution here (scroll down to method 2). The benefit of this method is that (1) it doesn't run the risk of any overflow, and (2) it doesn't require the use of a temporary third variable.

Problem 4

The following method add(int x, int y) adds two ints x and y using only bitwise operations. Explain how this function works.

This problem was adapted from GeeksforGeeks. They have a good explanation of the solution here.