5.1 You are given two 32-bit numbers, N andM, and two bit positions, i and j. Write a method to insert M into Nsuch that M starts at bit j and ends at bit i. You can assume that the bits j through i have enough space to fit all ofM. That is, ifM= 10011, you can assume that there are at least 5 bits between j and i. You would not, for example, have j-3 and i=2, because M could not fully fit between bit 3 and bit 2.
update某一位的时候，记得要把该位清零先。
Method 1: mask = ~((1<<(i-j+1)-1)<<i)
Method 2：mask=(~0<<(j+1)) | ((1<<i) - 1)
5.2 Given a real number between 0 and 7 (e.g., 0.72) that is passed in as a double, print the binary representation. If the number cannot be represented accurately in binary with at most 32 characters, print "ERROR."
小数的表示啊。用除法得到的是reverse的串。用乘法可以得到正串。
5.3 Given a positive integer, print the next smallest and the next largest number that have the same number of 7 bits in their binary representation.
用位操作方法很直观，用算术方法比较巧妙一些。arithmetically。
getNext: n + (1 << c0) + (1 << (c1-1)) - 1;
getPrev: n - (1 << c1) - (1 << (c0-1)) + 1;
5.4 Explain what the following code does: ((n & (n-1)) == 0).
check一下n是不是2的k次方。
也可以用来检验二进制中1的个数。
5.5 Write a function to determine the number of bits required to convert integer A to integer B.
就是用n&(n-1)来计算。这个操作每次可以把least significant bit为1的给清零。
5.6 Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit! are swapped, bit 2 and bit 3 are swapped, and so on)
巧妙。移偶数位，移奇数位。
5.7 An array A contains all the integers from 0 through n, except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is "fetch thejth bit ofAfi]," which takes constant time. Write code to find the missing integer. Can you do it in 0(n) time?
最简单的做法就是累加0到n，用求和公式得到的和减去计算出来的和，得到missing number。复杂度是O(nlgn)。因为n有lgn+1个bit。其实lgn一般也就32，如果n>>32，当然这种算法还是可以的。
所以还是要二分，想到了要按位计数，但是没有想到比较0的个数和1的个数。
在确定了LSBi的值后，需要去掉那些不符合的结果。
5.8 A monochrome screen is stored as a single array of bytes, allowing eight consecutive pixels to be stored in one byte. The screen has width w, where w is divisible by 8 (that is, no byte will be split across rows). The height of the screen, of course, can be derived from the length of the array and the width. Implement a function drawHorizontalLine(byte[] screen, int width, intxl, intx2, inty) which draws a horizontal line from (x 1, y) to (x2, y).
string binary(int n) {
stringstream s;
//while (n) { // negative number will always refill 1s for the most significant digit
for (int i = ; i < ; ++i) {
s << (char)('' + (n & 0x01));
//cout << (char)('0' + (n & 0x01)) << endl;
//cout << n << endl;
n = n >> ;
}
string ret = s.str();
int i = , j = ret.length() - ;
while (j > i) {
swap(ret[i], ret[j]);
i++; j--;
}
return ret;
}
// 5.3
int getNextSmallest(int n) {
int i = , c1 = ;
for (; i <= && (n & ( << i)) == ; ++i);
for (; (n & ( << i)) != ; ++i, ++c1);
if (i > ) return -;
n |= << i; // set i-th bit
n &= ~ << i;
n |= (( << (c1 - )) - );
return n;
}
int getPrevLargest(int n) {
// example: 11100111
int i = , c1 = ;
for (; (n & ( << i)) != ; ++i, ++c1); // ignore 1s, c1=3
for (; i <= && (n & ( << i)) == ; ++i); // find first 1, i=5
if (i > ) return -; // error, 00001111
n &= ~ << (i + ); // clear i-th bit, n=11000000
n |= (( << (c1 + )) - ) << (i - c1 - ); //n=11011110
return n;
}
// 5.5
int diffBits(int a, int b) {
int count = ;
for (int n = a ^ b; n != ; n = n & (n - )) {
count++;
}
return count;
}
// 5.6
int swapBits(int n) {
int ret = ;
for (int i = ; i < ; i += ) {
int tmp = (n >> i) & 0x03;
switch (tmp) {
case : ret |= ( << i); break;
case : ret |= ( << i); break;
case : ret |= ( << i); break;
}
}
return ret;
}
int swapBits2(int n) {
return ((n & 0xaaaaaaaa) >> ) | ((n & 0x55555555) << );
}
// 5.8
void drawLine(char* screen, int width, int x1, int x2, int y) {
int p1 = y * width + x1, p2 = y * width + x2;
int b1 = p1 >> , b2 = p2 >> ; //bucket
int s1 = p1 & 0x07, s2 = p1 & 0x07; //shift
for (int i = b1 + ; i < b2; ++i) {
screen[i] = 0xff;
}
int m1 = 0xff >> s1, m2 = ~(0xff >> (s2 + )); //mask
if (b1 == b2) {
screen[b1] |= (m1 & m2);
} else {
screen[b1] |= m1;
screen[b2] |= m2;
}
}