C++ Bitwise Operation [C++位运算]

位运算是C++的一类非常灵活的运算[在其他语言也有支持]，数量掌握可以提高程序效率和简介程度。也是很多科技公司入门面试的常见考题。

位运算大致有，

按位异或[XOR]
按位与[AND]
取反[NOT]
按位或[OR]

按位异或（^）

这是一个非常有用的运算符，它的表达是若参加运算的两个二进制位值相同则为0，否则为1，它拥有三个特点。

0^0=0，0^1=1，0异或任何数=任何数
1^0=1，1^1=0，1异或任何数=任何数取反
任何数异或自己=把自己置0

在一道leetcode题中，巧妙使用异或可以快速得到答案。题目如下

Given an array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Do not use extra memory.

如何设计一个不适用额外内存并且是线性时间复杂度的程序，来找到一个数组中只出现一次的数。题目不难常规解法再次按下不表，介绍一个采用异或的解法。因为A XOR A = 0，且XOR运算是可交换的，于是，对于实例{2,1,4,5,2,4,1}就会有这样的结果：

(2^1^4^5^2^4^1) => ((2^2)^(1^1)^(4^4)^(5)) => (0^0^0^5) => 5

因此，代码也会变得非常简单：

public class Solution {
    public int singleNumber(int[] nums) {
        int len = nums.length;
        int sol = 0;
        for(int i = 0; i < len; ++i) {
            sol ^=nums[i];
        }
        return sol;
    }
}

交换不用临时变量

交换两个值，不用临时变量，也可以通过位异或操作做到。

例如：

a=3，即11(2); b=4，即100(2)。

想将ａ和ｂ的值互换，可以用以下赋值语句实现：

a=a^b; (a=011^100=111 此时a=7)
b=b^a; (b=100^111=011 此时b=3)
a=a^b; (a=111^011=100 此时a=4)

等效于以下两步：

执行前两个赋值语句，a=a^b;和b=b^a;相当于b=b^(a^b)。
再执行第三个赋值语句，a=a^b;。由于a的值等于a^b，b的值等于b^a^b，

因此，相当于a=a^b^ｂ^a^b，即a的值等于a^a^b^b^b=b。

按位与（&）

按位与是指：参加运算的两个数据，按二进制位进行与运算。如果两个相应的二进制位都为１，则该位的结果值为1；否则为0。这里的1可以理解为逻辑中的true，0可以理解为逻辑中的false。按位与其实与逻辑上与运算（&&）规则一致。逻辑上与运算，要求运算数全真，结果才为真。若，A=true，B=true，则A&B=true。

例如：3&5 3的二进制编码是00000011。[内存储存数据的基本单位是字节(Byte)，一个字节由8个位(bit)所组成。位是用以描述电脑数据量的最小单位。二进制系统中，每个0或1就是一个位。将11（2）补足成一个字节，则是00000011]。5的二进制编码是101，将其补足成一个字节，则是00000101。

按位与运算（下面的写法只是为了方便看）：

00000011 &

00000101 =

00000001

由此可知3&5=1

那么按位与有什么用法呢？

清零

若想对一个存储单元清零，即使其全部二进制位为0，只要找一个二进制数，其中各个位符合一下条件：原来的数中为1的位，新数中相应位为0。然后使二者进行&运算，即可达到清零目的。其实对所有数对0进行按位与运算都可以达到这个效果。

取数中某些指定位

比如有一个整数a(2byte)，想要取其中的低字节（后8位），只需要将a与8个1按位与即可。 a 00101100 10101100 b 00000000 11111111 c 00000000 10101100

按位或（|）

两个相应的二进制位中只要有一个为1，该位的结果值为1。用法与按位与互为补充。

取反（~）

他是一元运算符，用于求整数的二进制反码，即分别将操作数各二进制位上的1变为0，0变为1。

比如9的二进制是1001，~9就是0110，就是6。

本文部分内容来源互联网

Categories

Tags