Review B: Bit operators: Questions

B1.1.

Assuming that we doing 32-bit integer computations, what is the value of each of the following C expressions?

a.10 & 24
b.10 | 24
c.10 ^ 24
B1.2.

Assuming that we doing 32-bit integer computations, what is the hexadecimal value of each of the following C expressions?

a.0x3C & 0x55
b.0x3C | 0x55
c.0x3C ^ 0x55
d.~0x3C
e.0x3C << 2
B1.3.

Evaluate each of the following C expressions, giving your answer as a base-10 number. Assume >> does an arithmetic shift.

a.(-16) ^ 3 =
b.(-10) >> 2 =
B1.4.

Explain the distinction betwen arithmetic and logical right-shift. Why is arithmetic right-shift so popular?

B1.5.

a. Give an example of an eight-bit number which, when arithmetically right-shifted one place, is different from the same number logically right-shifted one place.

b. Give an example of an eight-bit number which, when arithmetically right-shifted one place, is the same as the same number logically right-shifted one place.

B1.6.

What would the following C program print when run?

#include <stdio.h>

int mystery(int n, int i) {
    return (n >> i) & ~(-1 << i);
}

int main() {
    printf("%d %d %d %d\n", mystery(0xFF, 2), mystery(0xFF, 5),
        mystery(0x77, 3), mystery(0x02040608, 8));
    return 0;
}
B1.7.
Consider the following C function.

int f(int x, int n) {
    return x | (1 << (n - 1));
}
a.What does f(0, 2) return?
b.What about f(8, 3)?
c.What about f(8, 4)?
d.What about f(f(0, 1), 2)?
B2.1.

Using only bit operators, complete the below C function to return the second lowest byte in its 32-bit parameter. For instance, given the parameter 11111110 11011100 10111010 10011000(2), the function should return 10111010(2).

int second_byte(int bits) {


    return
}
B2.2.

Using only arithmetic and bit operators (no statements but return), complete the following function so that it returns its argument except that its 1's bit should be cleared and the 2's bit set. For example, given 1001(2) it returns 1010(2), as it does given 1000(2), 1010(2), and 1011(2).

int clear1_set2(int arg) {

    return
}
B2.3.

Suppose we regard the bits of an integer as indexed from 0 to 31, with 0 being the lowest-order bit. Complete the function set_bits so that it returns a number with all bits with indices between lo and hi, inclusive. For example, set_bits(2, 5) would return the number whose binary representation is 00…00111100.

Your solution should use only variable declarations, variable assignments, and a return statement. You may assume that both lo and hi are between 0 and 31 (inclusive).

int set_bits(int lo, int hi) {
B3.1.

Complete the below return statement so that it returns the sum of the upper and lower halves of the 32-bit int parameter. For instance, given the argument 0x00190028, the function would return 19(16) + 28(16) = 41(16). Do not add any additional statements.

int add_halves(int arg) {
    return
}
B3.2.

Without using any of the arithmetic operators (+, -, *, /, %), complete the following C function so that it returns the largest power of 2 that fits into its parameter. For example, max_pow2(20) is 16, and max_pow2(32) is 32. You may assume that the parameter is a positive integer. Note: You may use loops and conditional statements, but you should not call other functions.

int max_pow2(int n) {
B3.3.

Suppose we have an int value containing seven four-bit values packed together. Complete the following C function so that it adds all seven values together using only three additions. For example, given the value 0x31320BF, the function should return 3 + 1 + 3 + 2 + 0 + 11 + 15 = 35. The only operators used should be the bit operators and the three addition operators. The only statements should be variable declarations, assignment statements, and a return statement.

int add_nibbles(int x) {

Review B: Bit operators: Solutions

B1.1.
a.10 & 24 =8
b.10 | 24 =26
c.10 ^ 24 =18
B1.2.
a.14(16)
b.7D(16)
c.69(16)
d.FFFFFFC3(16)
e.F0(16)
B1.3.
a.(-16) ^ 3 =−13
b.(-10) >> 2 =−3
B1.4.

Both behave the same when shifting a number whose topmost bit is 0; but when the topmost bit is 1, the arithmetic right-shift will fill in the vacated top bits with 1's, whereas the logical right-shift will fill with 0's. The arithmetic right-shift is commonly used because with two's-complement representation, it effectively divides the number by a power of two: An arithmetic right-shift by two places, for example, is equivalent to dividing by four.

B1.5.

a. 11111111 (or any other sequence beginning with 1).

b. 00000000 (or any other sequence beginning with 0).

B1.6.
3 7 6 6
B1.7.
a.2
b.12
c.8
d.3
B2.1.
int second_byte(int bits) {
    return (bits >> 8) & 0xFF;
} 		—OR— int second_byte(int bits) {
    return (bits & 0x0000FF00) >> 8;
}
B2.2.
“(arg & ~0x1) | 2” or “(arg - (arg & 0x1)) | 2
B2.3.
int set_bits(int lo, int hi) {
    return ~(-2 << hi) ^ (-1 << lo);
}

Alternatively we could return (1 << (hi + 1)) - (1 << lo); one potential problem is that this won't necessarily work when hi is 31.

B3.1.
int add_halves(int arg) {
    return ((arg >> 16) & 0xFFFF) + (arg & 0xFFFF);
}
B3.2.
int max_pow2(int n) {
    int k;
    int ret;

    for(k = 1; k > 0; k <<= 1) {
        if((n & k) != 0) ret = k;
    }
    return ret;
}
B3.3.
int add_nibbles(int x) {
    x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
    x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
    return (x & 0xFFFF) + ((x >> 16) & 0xFFFF);
}