CMU 15-213 学习笔记

Bits

Recitation Activity 2

Question 4:

Find an algorithm for computing the expression (cond) ? t : f, which evaluates to t if
cond is 1 and f if cond is 0. Assume cond will either be 1 or 0.
int conditional(int cond, int t, int f) {
    /* Compute a mask that equals 0x00000000 or
    0xFFFFFFFF depending on the value of cond */
    int mask = ________________________________;
    /* Use the mask to toggle between returning t or returning f */
    return ________________________________________;
}

Answer：

int conditional(int cond, int t, int f) {
    // Generate a mask based on the value of cond
    int mask = ~(cond - 1);//生成掩码（全1 or 全0）

    // Use the mask to select between t and f
    return (mask & t) | (~mask & f);
}

Recitation Activity 3:Bit Count

Let’s count how many bits are set in a number. For each challenge, you can use any operator
allowed in the integer problems in datalab.
Using 1 operator, we return the number of bits set in a 1-bit number:
int bitCount1bit(int x) {return x;}
1. How about if there are two bits in the input? (4 ops max)
int bitCount2bit(int x) {
	int bit1 = _x & b01___;
	int bit2 = ____(x>>1)&b01 _______;
	return ___bit2____ + bit1 ;
}
2. How about if there are four bits? (8 ops max)
    int bitCount4bit(int x) {
    int mask = ___________;
    int halfSum = ___________;
    int mask2 = ___________;
    return ___________ + ___________ ;
}
3. How about if there are eight bits? (12 ops max)
    int bitCount8bit(int x) {
    int mask = ___________;
    int quarterSum = ___________;
    int mask2 = ___________;
    int halfSum = ___________;
    int mask3 = ___________;
    return ___________ + ___________ ;
}

ans:

//1
int bitCount2bit(int x) {
    int bitCount2bit(int x) {
    int bit1 = 0b01 & x;
    int bit2 = 0b01 & (x >> 1);
    return bit1 + bit2;
}
//2
int bitCount4bit(int x) {
    int mask = 0b0101;
    int halfSum = (mask & x) + (mask & (x >> 1));
    int mask2 = 0b0011;
    return (mask2 & halfSum) + (mask2 & (halfSum >> 2));
}
//3
int bitCount8bit(int x) {
    int mask = 0b01010101;
    int quarterSum = (mask & x) + (mask & (x >> 1));
    int mask2 = 0b00110011;
    int halfSum = (mask2 & quarterSum) + (mask2 & (quarterSum >> 2));
    int mask3 = 0b00001111;
    return (mask3 & halfSum) + (mask3 & (halfSum >> 4));
}

Recitation Activity 4:isPalindrome 回文检查

Let’s check to see if a number is a palindrome. For each challenge, you can use any operator
allowed in the integer problems in datalab.
Using 1 operator, we return the 1 if the number is a palindrome, 0 otherwise:
4. How about if there are two bits in the input? (5 ops max)
    int isPalindrome2bit(int x) {
    int hibit = __________;
    int lobit = ___________;
    return !(_______ ^ lobit); 
}
5. How about if there are four bits? (10 ops max)
    int isPalindrome4bit(int x) {
    int mask2 = _________;
    int hi2 = ___________;
    int lo2 = ___________;
    int mask1 = ___________;
    int newhi1 = (____ & ____) << _____;
    int newlo1 = (____ >> ____) & _____;
    int lo2Reverse = newhi1 | ________;
    return !(___________ ^ ___________); 
}
6. How about if there are eight bits? (15 ops max)
int isPalindrome8bit(int x) {
    int mask4 = _________;
    int hi4 = ___________;
    int lo4 = ___________;
    int mask2 = _________;
    int newhi2 = ___________;
    int newlo2 = ___________;
    int lo4R2 = _____ | _____;
    int mask1 = ___________;
    int newhi1 = ____________;
    int newlo1 = ____________;
    int lo4R4 = _____ | _____;
    return !(___________ ^ ___________);
}

ans:

//1
int isPalindrome2bit(int x) {
    int hibit = 0b01 & (x >> 1);
    int lobit = 0b01 & x;
    return !(hibit ^ lobit); 
}
//2
int isPalindrome4bit(int x) {
    int mask2 = 0b11;
    int hi2 = mask2 & (x >> 2);
    int lo2 = mask2 & x;
    int mask1 = 0b01;
    int newhi1 = (lo2 & mask1) << 1;
    int newlo1 = (lo2 >> 1) & mask1;
    int lo2Reverse = newhi1 | newlo1;
	return !(hi2 ^ lo2Reverse); 
}
//3 
int isPalindrome8bit(int x) {
    int mask4 = 0b1111;
    int hi4 = mask4 & (x >> 4);
    int lo4 = mask4 & x;
    int mask2 = 0b11;
    int newhi2 = (lo4 & mask2) << 2;
    int newlo2 = (lo4 >> 2) & mask2;
    int lo4R2 = newhi2 | newlo2;
    int mask1 = 0b0101;
    int newhi1 = (lo4R2 & mask1) << 1;
    int newlo1 = (lo4R2 >> 1) & mask1;
    int lo4R4 = newhi1 | newlo1;
    return !(hi4 ^ lo4R4);
}