笔试面试中涉及位运算的题目总结（一）

题目描述

有一个正整数，请找出其二进制表示中1的个数相同、且大小最接近的那两个数。(一个略大，一个略小)

给定正整数int x，请返回一个vector，代表所求的两个数（小的在前）。保证答案存在。

2返回：[1,4]题目分析：     对于这道题目，我觉得最重要的就是求一个数的二进制表示中1的个数。关于求一个数的二进制表示中1的个数会有很多种方法：方法1：与1求&运算，依次求出32个比特位中1的个数。（效率较低，无论多大的数，都要循环32次）方法2：平行算法：相邻的比特位求和，重复这个过程，直到最后只剩下一个位，就是该数的二进制表示中1的个数。方法3：快速法，任何数和比它小1的数做&运算，结果都会比原来的数少一个1，这样也是可以统计出1的个数。由于这是一种比较快速的方法，所以下面会使用这种办法来求取1的个数。【注意】
     很多初学者，对于这个问题还会想到模除的办法，但是模除这个方法，处理正数的时候没有什么问题，但是处理负数的时候，就不对了，下边给出测试代码：
void test(){       int x = -1;       int count = 0;       while (x)       {              if (x % 2 != 0)                     ++count;              x /= 2;       }       cout << count << endl;}
而实际上，-1的二进制表示中含有32个1.所以，这种办法就是错误的。好了，说了这么多，重点还是解决本题。下边给出本题的实现代码：实现代码：
class CloseNumber {public:    int Count(int x)    {        int count = 0;        while (x)        {            ++count;            x = x & (x - 1);        }        return count;    }    vector<int> getCloseNumber(int x) {        // write code here        int countOne = Count(x);        vector<int> ret;        for (int i = x - 1; i > 0; --i)        {            if (Count(i) == countOne)            {                ret.push_back(i);                break;            }           }        for (int i = x + 1; ;++i)        {            if (Count(i) == countOne)            {                ret.push_back(i);                break;            }        }        return ret;    }};题目二：
题目描述
请编写程序交换一个数的二进制的奇数位和偶数位。（使用越少的指令越好）
给定一个int x，请返回交换后的数int。
测试样例：
10返回：5题目分析：如果我们可以得到一个数的奇数位和偶数位的值，然后进行交换就可以了。得到奇数位的值和偶数位的值是比较简单的。奇数位的值：给定数字&0xAAAAAAAA偶数位的值：给定数字&0x55555555交换的方法：奇数位的值右移一位，偶数位的值左移一位，两者相加，得到结果。代码实现：
class Exchange {public:    int exchangeOddEven(int x) {        // write code here        int odd = (x & 0xAAAAAAAA);//换取x的奇数位信息        int even = (x & 0x55555555);//偶数位信息        return (odd >> 1) + (even << 1);    }};题目三：
题目描述
有一个介于0和1之间的实数，类型为double，返回它的二进制表示。如果该数字无法精确地用32位以内的二进制表示，返回“Error”。
给定一个double num，表示0到1的实数，请返回一个string，代表该数的二进制表示或者“Error”。
测试样例：
0.625返回：0.101题目分析：这个题目考查十进制的小于1的正小数转为二进制数的办法，这个学过计算机基础的人都会转化，就是连乘法，这里就不细说了。特别需要注意的是，浮点数与0进行比较的方法，这个问题，前边的文章也是总结过的。即就是这个数在无限接近于0的正小数和负小数之间，则就认为是为0.具体请看下边代码中的表示方法。代码实现：
class BinDecimal {public:#define exp pow(10,-7)    string PRintBin(double num) {        // write code here        string ret;        if (num >= 1)            return ret;        int count = 0;        ret.push_back('0');        ret.push_back('.');        while (!(num > -exp && num < exp))        {            num = num * 2;            if (num >= 1.0)            {                ++count;                ret.push_back('1');                num -= 1.0;            }               else            {                ++count;                ret.push_back('0');            }            if (count == 32){              return "Error";            }        }        return ret;    }};【总结】1.浮点数与0进行比较的方法，不可直接比较。2.十进制小数转换成二进制小数的方法-----连乘法。3.一个数的二进制表示中1的个数。4.如何得到一个数的奇数位和偶数位对应的值---将数字和0xAAAAAAAA按位与，和0x55555555按位与。