Data Lab: Manipulating Bits
Results
Correctness Results Perf Results
Points Rating Errors Points Ops Puzzle
1 1 0 2 4 bitOr
2 2 0 2 3 getByte
3 3 0 2 6 logicalShift
4 4 0 2 40 bitReverse
4 4 0 2 6 bang
1 1 0 2 2 tmax
2 2 0 2 7 fitsBits
2 2 0 2 7 dividePower2
2 2 0 2 2 negate
2 2 0 2 5 isPositive
3 3 0 2 14 isLessOrEqual
4 4 0 2 27 intLog2
2 2 0 2 16 floatIsEqual
4 4 0 2 14 floatFloat2Int
4 4 0 2 11 floatScale2
Score = 70/70 [40/40 Corr + 30/30 Perf] (164 total operators)
Report
bitOr
Thinking
De Morgan’s Law
Solution
int bitOr(int x, int y) { return ~((~x) & (~y)); }
getByte
Thinking
(x >> (n * 8)) & 0b11111111
= (x >> (n << 3)) & 0xff
Solution
int getByte(int x, int n) {
// return (x >> (n * 8)) & 0b11111111;
return (x >> (n << 3)) & 0xff;
}
logicalShift
Thinking
After logical shift to the right by n, the highest 32 - n bits should be 0. Therefore, let ~(((1 << 31) >> n) << 1) (an integer containing 32 - n 0s and n 1s) to be the mask.
Solution
int logicalShift(int x, int n) { return (x >> n) & (~(((1 << 31) >> n) << 1)); }
bitReverse
Thinking
// swap odd and even bits
x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1);
// swap consecutive pairs
x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2);
// swap 4-bit long pairs
x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4);
// swap bytes
x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8);
// swap 2-byte long pairs
x = (x >> 16) | (x << 16);
Note that when a negative number is shifted to the right, the high-order bit is filled with 1, so an additional mask16 needs to be added to erase the high-order 1.
Solution
int bitReverse(int x) {
int mask1, mask2, mask4, mask8, mask16;
mask1 = 0x55; // 0b01010101
mask1 |= mask1 << 8;
mask1 |= mask1 << 16;
// swap odd and even bits
x = ((x >> 1) & mask1) | ((x & mask1) << 1);
mask2 = 0x33; // 0b00110011
mask2 |= mask2 << 8;
mask2 |= mask2 << 16;
// swap consecutive pairs
x = ((x >> 2) & mask2) | ((x & mask2) << 2);
mask4 = 0x0f; // 0b00001111
mask4 |= mask4 << 8;
mask4 |= mask4 << 16;
// swap 8-bit long pairs
x = ((x >> 4) & mask4) | ((x & mask4) << 4);
mask8 = 0x00ff; // 0b0000000011111111
mask8 |= mask8 << 16;
// swap bytes
x = ((x >> 8) & mask8) | ((x & mask8) << 8);
mask16 = 0xff | (0xff << 8);
// swap 2-byte long pairs
x = ((x >> 16) & mask16) | (x << 16);
return x;
}
bang
Thinking
We only need to distinguish 0 and others. Since 0 == -0, or in other words, the sign bit of 0 does not change due to negation. It can be seen from this that if the sign bits of x and -x are both 0, then x must be 0. In addition, -x can be obtained by (~x) + 1.
Solution
int bang(int x) { return ((~(x | ((~x) + 1))) >> 31) & 1; }
tmax
Thinking
tmax is one 0 followed by 31 1s .
Solution
int tmax(void) { return ~(1 << 31); }
fitsBits
Thinking
When x is positive, if all bits in x >> (n - 1) equal 0, then n bits can represent x, vice versa. When x is negative, if all bits in ~ (x >> (n - 1)) equal 0, then n bits can represent x.
Solution
int fitsBits(int x, int n) {
// x = x >> (n - 1);
x = x >> (n + (~0));
return (!x) | (!(~x));
}
dividePower2
Thinking
When x is positive, x >> n is the final result. When x is negative, using x + ((1 << n) - 1) to shift to the right for rounding toward zero.
Solution
int dividePower2(int x, int n) {
// if (x >> 31) {
// // negative
// x += (1 << n) - 1;
// }
// return x >> n;
// x += (x >> 31) & ((1 << n) - 1);
// return x >> n;
x += ((x >> 31) & ((1 << n) + (~0)));
return x >> n;
}
negate
Solution
int negate(int x) { return (~x) + 1; }
isPositive
Thinking
(x > 0)
= (x >= 0) && (x != 0)
= (sign bit of x is 0) and (x is not 0)
Solution
int isPositive(int x) { return (!(x >> 31)) & (!!x); }
isLessOrEqual
Thinking
when x and y have the same sign, (x <= y) == (y - x >= 0). When x and y have different signs, y - x may cause overflow. if x is negative, the y must be positive, therefore x <= y.
Solution
int isLessOrEqual(int x, int y) {
int x_sign = x >> 31;
int y_sign = y >> 31;
int sign_diff = x_sign ^ y_sign;
int y_minus_x = y + ((~x) + 1);
int y_less_x =
(sign_diff & (y_sign & (!x_sign))) | ((!sign_diff) & (y_minus_x >> 31));
return !y_less_x;
}
intLog2
Thinking
Use dichotomy. First divide x into 16 by 16, using !!(x >> 16) to see whether there exists 1 in the first 16 bits. Then recursively, divide x into 8 by 8 to see whether the 1 reside in the second eight block from the right by !!(x >> 8). Then, divide into 4, 2, 1.
Solution
int intLog2(int x) {
int ans = (!!(x >> 16)) << 4;
ans = ans | ((!!(x >> (8 + ans))) << 3);
ans = ans | ((!!(x >> (4 + ans))) << 2);
ans = ans | ((!!(x >> (2 + ans))) << 1);
ans = ans | (!!(x >> (1 + ans)));
return ans;
}
floatIsEqual
Thinking
- If either argument is
NaN, return0. +0and-0are considered equal.
Solution
int floatIsEqual(unsigned uf, unsigned ug) {
const int kExpMask = 0xff; // 0b11111111
const int kFracMask = 0x7fffff; // 0b11111111111111111111111
int f_exp = (uf >> 23) & kExpMask;
int g_exp = (ug >> 23) & kExpMask;
int f_frac = uf & kFracMask;
int g_frac = ug & kFracMask;
if ((f_exp == kExpMask) && f_frac) // f is NaN
return 0;
if ((g_exp == kExpMask) && g_frac) // g is NaN
return 0;
if (((uf & 0x7fffffff) == 0) && ((ug & 0x7fffffff) == 0)) {
// (f == 0) && (g == 0)
return 1;
}
return uf == ug;
}
floatFloat2Int
Thinking
If exp < 0, then f < 1, return 0. Else if exp < 31, f is within the range of int. Else, f is out of range.
Solution
int floatFloat2Int(unsigned uf) {
const int kExpMask = 0xff; // 0b11111111
const int kFracMask = 0x7fffff; // 0b11111111111111111111111
int sign = uf >> 31;
int exp = (uf >> 23) & kExpMask;
int frac = uf & kFracMask;
exp -= 0x7f;
frac |= 0x800000; // 0b100000000000000000000000
if (exp < 0) {
// close to 0
return 0;
} else if (exp < 31) {
if (exp < 23) {
frac >>= 23 - exp;
} else {
frac <<= exp - 23;
}
if (sign) frac = -frac;
return frac;
} else {
// out of range
return 0x80000000u;
}
}
floatScale2
Solution
unsigned floatScale2(unsigned uf) {
const int kExpMask = 0xff; // 0b11111111
const int kFracMask = 0x7fffff; // 0b11111111111111111111111
int s = uf >> 31;
int exp = (uf >> 23) & kExpMask;
int frac = uf & kFracMask;
if (!exp) {
// exp == 000...0
// Denormalized Values
frac <<= 1;
} else if (exp != kExpMask) {
// (exp != 000...0) && (exp != 111...1)
// "Normalized" Values
++exp;
}
// else Special Values
return (s << 31) | (exp << 23) | frac;
}