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

￡神魔★判官ぃ 2022-07-12 03:15 164阅读 0赞

**题目一：**

## 题目描述 ##

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

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

测试样例：

返回：\[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。

测试样例：

返回：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按位与。