程序员面试金典

面试题 05.03. 翻转数位

class Solution { public: int reverseBits(int num) { int ans=0,cnt=0; int cur=0,pre=0;//前一个连续1的个数 后一个连续1的个数 if(num==-1) return 32; while(num&&cnt<32) { if(num&1) cur++; else { pre=cur; cur=0; } num>>=1; ans=max(ans,pre+cur); cnt++; } return ans+1; } };

面试题 05.04. 下一个数

class Solution { public: vector<int> findClosedNumbers(int num) { vector<int> res(2, -1); int tmp = num; int index = 0; while(tmp > 0){ //找到低位的01 if((tmp & 3) == 1) break; tmp >>= 1; ++index; } cout << index <<endl; if(index < 31 && tmp != 0){ res[0] = (num & ~(1 << index)); res[0] = (res[0] | (1 << (index + 1))); //将找到的01替换成10 int count = 0; tmp = num; for(int i = 0;i < index;++i){ //将右侧的1移至右侧低位 if(tmp & 1) ++count; tmp >>= 1; } res[0] = res[0] & ~((1 << index) - 1); res[0] = res[0] | ((1 << count) - 1); } tmp = num; index = 0; while(tmp > 0){ //找到最低位的10 if((tmp & 3) == 2) break; tmp >>= 1; ++index; } cout << index; if(index < 31 && tmp != 0){ res[1] = (num | (1 << index)); res[1] = (res[1] & ~(1 << (index + 1))); //将最低位的10换成01 int count = 0; tmp = num; for(int i = 0;i < index;++i){ //将右侧的1移至右侧高位 if(tmp & 1) ++count; tmp >>= 1; } res[1] = res[1] & ~((1 << index) - 1); res[1] = res[1] | (((1 << count) - 1) << (index - count)); } return res; } };

面试题 05.06. 整数转换

class Solution { public: int convertInteger(int A, int B) { int cnt=0; unsigned x=A^B; while(x!=0) { x&=(x-1); cnt++; } return cnt; } };

面试题 05.07. 配对交换 位运算

class Solution { public: int exchangeBits(int num) { int odd=num&0x55555555; int even=num&0xaaaaaaaa; odd=odd<<1; even=even>>1; return odd|even; } };

面试题 05.08. 绘制直线

class Solution { public: vector<int> drawLine(int length, int w, int x1, int x2, int y) { vector<int> res(length, 0); for( int i=x1; i<=x2; ++i ) res[i/32+y*w/32] |= (1<<(31-i%32)); return res; } };