常见的位运算用法总结

逃离我推掉我的手 2022-08-20 15:08 444阅读 0赞

本文是准备找工作过程中关于位运算的一些积累和记录的整理。**注意：部分位运算的处理结果依赖于变量所属类型的字长，使用时请结合具体环境修改。**

## 1.XOR应用 ##

性质：满足交换率、结合律，一个数与其自身异或结果为0。

**(1)不用中间变量，交换两数**

a = a^b;
    b = b^a; //b = b^(a^b),thus b becomes the earlier a
    a = a^b; //a = (a^b)^a,thus a becomes the earlier b

**扩展：不用异或，同样也能不用中间变量，交换两数**

a = a - b;
    b = a + b; // b = (a - b)+ b, thus b becomes the earlier a
    a = b - a; // a = a - (a - b),  thus a becomes the earlier b

但是这种方式引入了一个陷阱，如果a是一个很大的正数而b是一个很小的负数，那么a-b就会溢出。虽然在b=a+b时可能会通过再一次溢出从而获得真实的a的值，不推荐这种利用未定义行为的解法。

如何理解这种解法？其实第一行是a=a-b还是a=a+b再或者是a=a\*b都可以，对应地在第二行把b通过这个式子和b本身的运算求出a即可，再在第三行利用ab的组合值以及原先的a求解b。明显地，使用\*比+或-更容易溢出。理解后，完全不必死记硬背这三个式子，看成是解方程就不难了。

**(2)寻找只出现1次的一个数，其他数出现偶数次（或寻找唯一一个出现奇数次的数，其他数出现偶数次）**

解法：全部数做XOR，最后的结果就是要找的数。

**扩展：寻找出现奇数次的数，其他不必寻找的数只出现偶数次。 **

常见的面试题扩展，思路还是原来的思路，先全部XOR一遍，在获得的结果上，对每一位为1（即可能有两个不同的数，二进制标识中该位不同）进行分组，构造出所有待找出的数。

这么概括很抽象，看一道具体的笔试题吧，通过解题就容易理解了。

（小米2013校招笔试题）一个数组里，除了三个数是唯一出现的，其余的都出现偶数个，找出这三个数中的任一个。比如数组元素为【1, 2,4,5,6,4,2】，只有1,5,6这三个数字是唯一出现的，我们只需要输出1,5,6中的一个就行。

解答：[http://blog.csdn.net/leo115/article/details/8036990][http_blog.csdn.net_leo115_article_details_8036990]

**(3)NIM游戏的状态分析**

请参考《编程之美》1.12 NIM(2) “拈”游戏分析。其核心是，两种完全不同的状态（安全状态和不安全状态）的XOR值恰为0和1。

## **2.加法，不用+-\*/做加法（《剑指Offer》面试题47）** ##

迭代版本（《剑指Offer》面试题47）

![复制代码][copycode.gif]

int Add(int num1,int num2)
    {
        int sum,carry;
        do {
            sum = num1^num2;
            carry= (num1 & num2)<<1;
            num1 = sum;
            num2 = carry;
        } while (num2!=0)
        return num1;
    }

![复制代码][copycode.gif]

递归版本（CareerCup 20.1）

![复制代码][copycode.gif]

int add_no_arithm(int num1,int num2)
    {
        if(num2 == 0)
            return num1;
        int sum = a^ b;
        int carry = (a&b)<<1;
        return add_no_arithm(sum,carry);
    }

![复制代码][copycode.gif]

## **3.求两数的平均数 ，不用-、\*、/求两数的平均数 ** ##

**　　**似乎是出自《程序员面试宝典》，但是我在第三版第12章没找到原题。用下面的代码就能“神奇地”获得两个整型的平均值

int  average（int x，int y）
    {
        return （ (x&y) + ( (x^y)>>1 ) ）;
    }

解释请看：[http://blog.csdn.net/leo115/article/details/7993110][http_blog.csdn.net_leo115_article_details_7993110]，不过也是转载，原出处疑似已失效。

## 4.不用\*和/做除法（《算法设计手册》面试题1-28） ##

慢速版本和优化版本请参考旧作：[http://www.cnblogs.com/wuyuegb2312/p/3257558.html][http_www.cnblogs.com_wuyuegb2312_p_3257558.html]

纵观第2、3、4条可以发现，如果问题限制不允许使用某种四则运算符以及%，就可以在位运算上打主意了。

## 5.二进制中1的个数 ##

不要觉得很trick，这是K&R提到过的。值得注意的是，如果使用C实现，为了避免实现定义不同造成的结果不同，需要把该变量转化为无符号型。

![复制代码][copycode.gif]

int bitcount(unsigned x)
    {
        int b;
        for(b=0;x|=0;x>>=1)
            if(x&01)
                b++;
        return b;
    }

![复制代码][copycode.gif]

事实上K&R习题2-9提到了一种更快的算法：

![复制代码][copycode.gif]

int bitcount(unsigned x)
    {
        int b;
        for(b=0;x!=0;x&= x-1)
            b++;
        return b;
    }

![复制代码][copycode.gif]

## 6.从无符号型x的第p位开始，取n位（K&R） ##

//最低位是第0位
    unsigned getbits(unsigned x,int p, int n)
    {
        return (x>>(p+1-n)) & ~(~0<<n);
    }

## 7.利用同余的性质和位运算加速的辗转相减求最大公约数法（《C语言参考手册》第七章） ##

![复制代码][copycode.gif]

unsigned binary_gcd(unsigned x, unsigned y)
    {
        unsigned temp;
        unsigned common_power_of_two = 0;
        if(x==0)
            return 0;
        if(y==0)
            return 0;
    
        /*find the largest power of two
        that divides both x and y*/
        while(((x|y)&1)==0) {
            x >>= 1;
            y >>= 1;
            ++common_power_of_two;
        }
        while((x &1) == 0)
            x >>= 1;
        while(y) {
            /*x is odd and y is nonzero here*/
            while((y&1)==0)
                y >>= 1;
            /*x and y are odd here*/
            temp = y;
            if (x>y)
                y = x - y;
            else
                y = y-x;
            x = temp;
            /*Now x has the old value of y,which is odd.
             y is even,because it is the difference of 
            two odd numbers therefore it will be right-shifted
            at least once on the next iteration.*/
        }
        return (x<<common_power_of_two);
    }

![复制代码][copycode.gif]

## 8.不用大于小于号，求两数较大值（CareerCup 19.4） ##

![复制代码][copycode.gif]

int getMax(int a,int b)
    {
        int c = a - b;
        int k = (c>>31)&0x1;
        int max = a-k*c;
        return max;
    }

![复制代码][copycode.gif]

在不允许使用>、<以及任何判断语句时，使用移位判断一个数的正负性是常用技巧，如《深入理解计算机系统》2.3.7节习题2.42中求补码对给定2的幂的商的解法。这个问题以及求解涉及到补码的表示和运算的知识，在此不进行详述，有兴趣的读者可以自行查阅。

更多关于《深入理解计算机系统》习题答案的内容，可以参考：[http://blog.csdn.net/yang\_f\_k][http_blog.csdn.net_yang_f_k]

## 9.实现位向量 ##

这种做法是对空间的高效利用。对《编程珠玑》上位向量实现全面分析的旧作一篇：[http://www.cnblogs.com/wuyuegb2312/p/3136831.html][http_www.cnblogs.com_wuyuegb2312_p_3136831.html]

## 10.其他 ##

附上[MoreWindows][]前辈的一篇博文链接：[位操作基础篇之位操作全面总结][Link 1]，顺便把该文的目录拿来做个索引：

1.  [一 位操作基础][Link 2]
2.  [二 常用位操作小技巧][Link 3]
    
    1.  [判断奇偶][Link 4]
    2.  [交换两数][Link 5]
    3.  [变换符号][Link 6]
    4.  [求绝对值][Link 7]
3.  [三 位操作与空间压缩][Link 8]
4.  [四 位操作的趣味应用][Link 9]
    
    1.  [  高低位交换][Link 10]
    2.  [  二进制逆序][Link 11]
    3.  [  二进制中1的个数][_1]
    4.  [  缺失的数字][Link 12]

[http_blog.csdn.net_leo115_article_details_8036990]: http://blog.csdn.net/leo115/article/details/8036990
[copycode.gif]: /images/20220731/4048186a9add42ca8f4182ea72a6d16b.png
[http_blog.csdn.net_leo115_article_details_7993110]: http://blog.csdn.net/leo115/article/details/7993110
[http_www.cnblogs.com_wuyuegb2312_p_3257558.html]: http://www.cnblogs.com/wuyuegb2312/p/3257558.html
[http_blog.csdn.net_yang_f_k]: http://blog.csdn.net/yang_f_k
[http_www.cnblogs.com_wuyuegb2312_p_3136831.html]: http://www.cnblogs.com/wuyuegb2312/p/3136831.html
[MoreWindows]: http://blog.csdn.net/morewindows
[Link 1]: http://blog.csdn.net/morewindows/article/details/7354571
[Link 2]: http://blog.csdn.net/morewindows/article/details/7354571#t0
[Link 3]: http://blog.csdn.net/morewindows/article/details/7354571#t1
[Link 4]: http://blog.csdn.net/morewindows/article/details/7354571#t2
[Link 5]: http://blog.csdn.net/morewindows/article/details/7354571#t3
[Link 6]: http://blog.csdn.net/morewindows/article/details/7354571#t4
[Link 7]: http://blog.csdn.net/morewindows/article/details/7354571#t5
[Link 8]: http://blog.csdn.net/morewindows/article/details/7354571#t6
[Link 9]: http://blog.csdn.net/morewindows/article/details/7354571#t7
[Link 10]: http://blog.csdn.net/morewindows/article/details/7354571#t8
[Link 11]: http://blog.csdn.net/morewindows/article/details/7354571#t9
[_1]: http://blog.csdn.net/morewindows/article/details/7354571#t10
[Link 12]: http://blog.csdn.net/morewindows/article/details/7354571#t11