Review B: Bit operators
printable version
B1: [1] [2] [3] [4] [5] [6] [7] // B2: [1] [2] [3] // B3: [1] [2] [3]
Problem 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 |
| a. | 10 & 24 = | 8 |
| b. | 10 | 24 = | 26 |
| c. | 10 ^ 24 = | 18 |
Problem 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 |
| a. | 14(16) |
| b. | 7D(16) |
| c. | 69(16) |
| d. | FFFFFFC3(16) |
| e. | F0(16) |
Problem 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 = |
| a. | (-16) ^ 3 = | −13 |
| b. | (-10) >> 2 = | −3 |
Problem B1.4
Explain the distinction betwen arithmetic and logical right-shift. Why is arithmetic right-shift so popular?
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.
Problem 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.
a. 11111111 (or any other sequence beginning with 1).
b. 00000000 (or any other sequence beginning with 0).
Problem 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;
}
3 7 6 6
Problem 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)? |
| a. | 2 |
| b. | 12 |
| c. | 8 |
| d. | 3 |
Problem 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
}
int second_byte(int bits) { |
int second_byte(int bits) { |
Problem 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
}
(arg & ~0x1) | 2”
or
“(arg - (arg & 0x1)) | 2
Problem 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) {
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.
Problem 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
}
int add_halves(int arg) {
return ((arg >> 16) & 0xFFFF) + (arg & 0xFFFF);
}
Problem 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) {
int max_pow2(int n) {
int k;
int ret;
for(k = 1; k > 0; k <<= 1) {
if((n & k) != 0) ret = k;
}
return ret;
}
Problem 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) {
int add_nibbles(int x) {
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
return (x & 0xFFFF) + ((x >> 16) & 0xFFFF);
}